글 읽기 - 시간 초과 ㅠㅠ

kim031504 4년 전 0

완전 탐색을 이용하여

예를 들어 문제의 예시에서

{'a', 'z'}

의 조합으로 "aaaa"부터 "zzzz"까지 완전 탐색을 하면서

중간 마다 a와 z의 개수를 세어서

만족하는 순간이 오면 탐색을 끝내고 해답을 출력하게 코드를 짰습니다.

하지만, 시간 초과가 나네요 ㅠ

브루트 포스 말고 다른 방식이 있을까요...?

코드에 대한 자세한 설명은 주석으로 달아놨습니다!

#include <iostream>
#include <string>

using namespace std;

int N, M, K;

char arr[2] = { 'a', 'z' };

string str, answer;

// 몇 번째로 조건을 만족하는 문자열인지 담는다.
int cnt = 0;

// 해답을 찾는 순간 true가 되어 완전 탐색을 종료하기 위함!
bool judge = false;

// 완전 탐색! 생각
void brute_force(int i)
{
	// N + M 만큼의 문자열 길이가 된다면
	if (i == (N + M))
	{
		int cnt_a = 0;
		int cnt_z = 0;
		int len = str.size();

		// a와 z의 개수를 센다
		for (int i = 0; i < len; i++)
		{
			if (str[i] == 'a')
				cnt_a++;
			else
				cnt_z++;
		}

		// 조건을 만족하면
		if (cnt_a == N && cnt_z == M)
		{
			// cnt 증가
			cnt++;

			// K와 같아지는 순간 답을 찾은 것이므로!
			if (cnt == K)
			{

				// 작업!
				answer = str;
				judge = true;

				return;
			}
		}
	}
	else
	{
		for (int j = 0; j < 2; j++)
		{
			// 문자를 추가하며
			str += arr[j];

			// 다음 행으로 넘어간다 생각
			brute_force(i + 1);

			// 답을 찾은 순간 더 이상 함수 호출 안 한다.
			if (judge)
				return;

			// 다 돌고 나면 백 트래킹! 하나씩 뒤로 물러 가서 다음 탐색 시작
			str = str.substr(0, str.size() - 1);
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M >> K;

	brute_force(0);

	cout << answer << '\n';

	return 0;
}

opop20207 4년 전 0

K는 10억까지 주어집니다. 그말인즉슨 brute_force함수의 첫번째 if문에 적어도 10억번이상 진입한 후에야, 사실 그보다 훨씬 많이 진입하겠지만, judge가 true가 되며 탈출하겠군요.

아래와 같은 예제가 주어지면 직접 실행해보셔도 아시겠지만 엄청나게 오래 걸립니다.

브루트 포스로 이문제는 풀 수 없습니다. 다른 방법을 생각해보세요.

/*
100 100 1000000000
*/

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과 ㅠㅠ

kim031504 4년 전 0

opop20207 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말