[백준1248] Guess (C++)

📌 문제

BOJ 바로가기

sign 배열의 정보가 주어진다. sign[a][b] = '+'는 a에서부터 b까지의 합이 양수임을 의미한다. 주어진 sign배열을 만족하는 수열을 찾아야 한다.

🗡 풀이

📍 브루트포스를 이용해 모든 경우의 수를 조사한다. 이때, 정말 모든 경우의 수를 조사해서 마지막에 답이 될 수 있는지를 검사한다면 시간초과가 발생한다.

📍 ans배열의 값에는 -10부터 10까지의 수가 들어갈 수 있다. for문을 이용해 ans배열에 위 범위를 만족하는 값을 넣어준다. 그리고 check 함수를 호출해서 ans배열에 적절한 값이 들어갔는지를 판별한다. check함수의 리턴값이 true라면 go함수를 재귀적으로 호출해 다음 인덱스에 들어갈 값을 탐색한다.

📍 답을 딱 하나만 출력해야 하기 때문에 exit(0)을 넣어서 답 하나를 찾으면 프로그램이 종료되도록 했다.

🚩 소스코드

#include <iostream>
using namespace std;

int n, ans[10];
char sign[10][10];

bool check(int idx) {
	int sum = 0;
	for (int i = idx; i >= 0; i--) {
		sum += ans[i];
		if (sum <= 0 && sign[i][idx] == '+')
			return false;
		if (sum >= 0 && sign[i][idx] == '-')
			return false;
		if (sum != 0 && sign[i][idx] == '0')
			return false;
	}
	return true;
}

void go(int cnt) {
	if (cnt == n) {
		for (int i = 0; i < n; i++)
			cout << ans[i] << ' ';
		exit(0); // 정답 하나만 출력
	}
	for (int i = -10; i <= 10; i++) {
		ans[cnt] = i;
		if (check(cnt)) // ans[cnt]가 정해질 때마다 검사
			go(cnt + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++)
			cin >> sign[i][j];
	}
	go(0);
}