백준 1248 : 맞춰봐

https://www.acmicpc.net/problem/1248

1248번: 맞춰봐

 

주어진 예제 케이스에 의하면,

4 -+0++++--+

S[0][0] = -8, S[0][1] = 2, S[0][2] = 0, S[0][3] = 1

S[1][1] = 10, S[1][2] = 8, S[1][3] = 9

S[2][2] = -2, S[2][3] = -1

S[3][3] = 1 이므로,

-+0++++--+

 

위와 같은 형태가 나오게 된 것입니다.

​

먼저, S는 적은 숫자 구간의 합을 의미하므로

S[i][j] = i == j ? 입력값 : S[i][j-1] + 입력값; 이란 것을 유추할 수 있습니다.

​

예제 케이스로 계속 진행해보겠습니다.

만약 0번째 수를 추가했다면, S[0][0]을 검사할 수 있습니다.

만약 1번째 수를 추가했다면, S[0][1], S[1][1]을 검사할 수 있습니다.

만약 2번째 수를 추가했다면, S[0][2], S[1][2], S[2][2]를 검사할 수 있습니다.

만약 3번째 수를 추가했다면, S[0][3], S[1][3], S[2][3], S[3][3]을 검사할 수 있습니다.

​

입력한 기호 문자열에서 각 S[i][j] 값은 괄호 안의 기호 문자열에 대한 인덱스에 대해 유효한지 검사하면 됩니다.

만약 0번째 수를 추가했다면, S[0][0] (0)을 검사할 수 있습니다.

만약 1번째 수를 추가했다면, S[0][1] (1), S[1][1] (4)을 검사할 수 있습니다.

만약 2번째 수를 추가했다면, S[0][2] (2), S[1][2] (5), S[2][2] (7)를 검사할 수 있습니다.

만약 3번째 수를 추가했다면, S[0][3] (3), S[1][3] (6), S[2][3] (8), S[3][3] (9)을 검사할 수 있습니다.

유효한 숫자에 대해 진행하다가 조건에 맞는 숫자열이 만들어지면, 출력 후 종료해주었습니다.

 

#include <iostream>
int n, b[10], s[10][10];
char a[56];
void f(int c) {
	if (c == n) {
		for (int i = 0; i < n; i++) printf("%d ", b[i]);
		printf("\n");
		exit(0);
	}
	for (int i = -10; i <= 10; i++) {
		int j = 0, k = n - 1, idx = c;
		for (; j <= c; idx+=k--,j++) {
			s[j][c] = j == c ? i : s[j][c - 1] + i;
			if (a[idx] == '-' && s[j][c] >= 0 || a[idx] == '+' && s[j][c] <= 0 || a[idx] == '0' && s[j][c] != 0) break;
		}
		if (j != c + 1) continue;
		b[c] = i;
		f(c + 1);
	}
}
int main() {
	scanf("%d", &n);
	scanf("%s", a);
	f(0);
}