[백준/C++] Guess

Guess

풀이

기본적으로 -10부터 10까지 모든 수를 돌면서 배열을 만들고 조건을 만족하면서 N개를 세면 출력하는 식의 코드이다. 그런데 그렇게 하면 너무 시간이 많이 걸리니까 백트레킹을 이용할텐데 trueIfPossible 함수가 백트레킹의 Prunning을 담당하는 부분이다. 배열을 만들면서 조건을 만족하지 못하면 false를 뱉어내게 되고 바로 다음 케이스로 넘어간다.

#include <iostream>
#include <vector>
using namespace std;

int N;
char S[10][10];
int list[21];
vector<int> ans;

bool trueIfPossible(int index)
{
	if(ans.size() == 0) return true;
	
	for(int i = 0; i < index; ++i) {
		if(S[i][i] == '+' && ans[i] <= 0) return false;
		if(S[i][i] == '-' && ans[i] >= 0) return false;
		if(S[i][i] == '0' && ans[i] != 0) return false;
		int sum = ans[i];
		for(int j = i+1; j < index; ++j) {
			sum += ans[j];
			if(S[i][j] == '+' && sum <= 0) return false;
			if(S[i][j] == '-' && sum >= 0) return false;
			if(S[i][j] == '0' && sum != 0) return false;
		}
	}

	return true;
}

bool dfs(int cnt)
{
	if(!trueIfPossible(cnt)) return false;

	if(cnt == N) {
		for(int i = 0; i < N; ++i)
			cout << ans[i] << ' ';
		return true;
	}

	for(int i = 0; i < 21; ++i) {
		ans.push_back(list[i]);
		if(dfs(cnt + 1)) return true;
		ans.pop_back();
	}

	return false;
}

int main()
{
	int tmp = -10;
	for(int i = 0; i < 21; ++i)
		list[i] = tmp++;

	cin >> N;
	for(int i = 0; i < N; ++i)
		for(int j = i; j < N; ++j)
			cin >> S[i][j];

	dfs(0);

	return 0;
}

끝