백준 1248. Guess

알고리즘 기초 문제 중 브루트포스-재귀 문제(530)

Guess

1. 간단 설명

n*n 매트릭스가 주어짐

각 매트릭스의 셀에는 S_ij 가 주어지는데

S_ij = a_i + a_i+1 + ... + a_j로 이루어진다

a_i + … + a_j > 0 인 경우에는 S_ij = "+" 로

a_i + … + a_j < 0 인 경우에는 S_ij = "−" 로

a_i + … + a_j = 0 인 경우에는 S_ij = "0"으로 기록한다

배열 a가 주어졌을 떄, s_ij를 구하는것이 아닌

s_ij가 주어졌을때, 이를 이용하여 배열 a를 구하는 문제

2. 예시

(a1, a2, a3, a4)=( −1, 5, −4, 2) 라면

	1	2	3	4
1	-	+	0	+
2		+	+	+
3			-	-
4				+

a_11 = a_1 = -1 이므로 - a_12 = a_1 + a_2 = -1 + 5 = 4 이므로 4 a_13 = a_1 + a_2 + a_3 = -1 + 5 -4 = 0 이므로 0 a_14 = -1 + 5 -4 + 2 = 2 이므로 +

a_21은 없음 a_22 = 5 => + a_23 = 5 -4 = 1 => + a_24 = 5 -4 +2 = 3 => +

a_33 = -4 => - a_34 = -4 + 2 = -2 => -

a_44 = 2 => +

이런식으로 매트릭스를 구성된다

주의사항

• 배열 a는 여러개일수 있으므로, 이를 만족하는 아무 배열이나 출력하면 된다
• 원본 배열의 모든 정수는 -10이상 10이하

3. 알고리즘

• 방법 1. 먼저 숫자를 n개 조합하여 배열 a를 구성하고, 배열이 주어진 매트릭스와 일치하는지 검증한다

수열을 x_1, x_2, … x_n이라고 하면

x_1 = -10에서 10 (20개), x_2 = -10(20개) … x_10 (20개) 이므로

20 * 20 * 20 * … * 20 = 20^10 = 10, 24 0,0 00,00 0,000 = 10조 번 검증이 필요하다

이는 2초 시간을 아득히 초과하므로 모든 경우를 검증하는 것은 불가능

• 방법 2. 숫자를 하나씩 추가할 때 해당 셀을 검증

배열의 원소가 한개일 때 -> S_11 하나 체크

배열의 원소가 두개일 때 -> S_11, S_12, S_22 체크

배열 원소가 3개 -> S_11, S_12, S_13, S_22, S_23, S_33 체크

…

이런식으로 원소가 하나 추가될 때 마다

이전의 원소들은 체크할 필요 없이, 해당 열의 원소들만 검증하면 된다.

(이미 이전에 검증했기 때문)

이를 이용하여, 배열에 숫자를 추가하고

이 배열로 S의 해당열의 원소들이 문제 없는지 체크하고, 문제 없다면 넣는 식으로 반복한다

재귀(int level){
	- 만약 현재 level이 n이라면, 현재 저장된 배열을 출력
	- 숫자 하나를 추가하는 과정 
		- (-10 ~ 10) 사이의 숫자 중 하나 선택
		- 이를 숫자 배열에 추가한다
		- 매트릭스 결과를 검증하고 쳐내는 가지치기 과정 
			- 문제 없다면 재귀 호출(int level)
		- 복원
}

필요 변수

• 부등호의 개수 int k 2 ≤ k ≤ 9
• 부등호를 저장할 문자열 string sign
• bool used[10] <- 0123456789 가 사용되었는지 체크하는 변수
• 부등호 관계를 만족시키는 정수의 최대 최소값 long long int max_val, min_val
  • 최대 98 7654 3210이므로, int형으로 처리 불가!

4. 소스코드

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int n;
char matrix[11][11];
bool flag = false;

vector<int> v;

void input() {
	cin >> n;

	for (int y = 0; y < n; y++) {
		for (int x = y; x < n; x++) {
			cin >> matrix[y][x];
		}
	}
}


// 현재 v에 들어있는 원소로 matrix 검증하는 함수
bool check(int size) {

	int sum = 0;
	for (int i = size; i >= 0; i--) {
		sum = sum + v[i];
		
		if (matrix[i][size] == '+' && sum <= 0) return false;
		if (matrix[i][size] == '-' && sum >= 0) return false;
		if (matrix[i][size] == '0' && sum != 0) return false;
	}
	return true;
	
/*
mat/sum		-	0	+
-			t	f	f
0			f	t	f
+			f	f	t

*/

}

void recursive(int level) {
	if (flag == true) return;
	if (level == n) {
		flag = true;
		for (int e : v) {
			cout << e << ' ';
		}
		return;
	}

	for (int x = -10; x <= 10; x++) {
		v.push_back(x);
		if(check(level) == true)
			recursive(level + 1);
		v.pop_back();
	}
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	input();

	recursive(0);

	return 0;
}