[백준 1248] 맞춰봐 (C++)

문제 링크: https://www.acmicpc.net/problem/1248

1248번: 맞춰봐

1. 주의할 점

- -10~10까지 무작정 대입한 후, 비교하지 않도록 한다 -> TLE

- 입력을 배열형태로 받아서 해결하기 편하게 바꾼다

 

2. 구현

- Cal(idx) 함수를 통해 집어 넣은 숫자가 적합한지 검사한다

- Back_tracking(idx) 함수에서 Result[idx][idx]의 값이 +,-,0 인 경우로 나눠서 진행한다

- 0인 경우, Arr[idx]에 0을 대입하고 Sum[] 또한 갱신한다

- -인 경우 S의 값을 -1, +인 경우 S의 값을 1로 설정한 후, Arr[]와 Sum[]배열을 갱신하고 Cal()함수를 통해 적합한지 검사한다.

 

#include <iostream>
using namespace std;
int num, arr[11], sum[11]; //길이, 정답, 1~idx까지의 합
char result[11][11];
bool finish = false;

int cal(int idx) {
	for (int r = 1; r < idx; r++) {
		if (result[r][idx] == '+' && sum[idx] <= sum[r - 1]) return 0;
		if (result[r][idx] == '-' && sum[idx] >= sum[r - 1]) return 0;
		if (result[r][idx] == '0' && sum[idx] != sum[r - 1]) return 0;
	}
	return 1;
}

void back_tracking(int idx) {
	if (finish) return;
	if (idx > num) {
		finish = true;
		for (int i = 1; i <= num; i++)
			cout << arr[i] << " ";
		return;
	}
	//우선 숫자부터 대입
	if (result[idx][idx] == '0') {
		arr[idx] = 0;
		sum[idx] = sum[idx - 1];
		back_tracking(idx + 1);
	}	
	else {
		int s = 1;
		if (result[idx][idx] == '-')
			s = -1;
		for (int i = 1; i <= 10; i++) {
			arr[idx] = i * s;
			sum[idx] = sum[idx - 1] + arr[idx];
			if (cal(idx))
				back_tracking(idx + 1);
		}
	}
}

int main() {
	cin >> num;
	for (int j = 1; j <= num; j++) 
		for (int i = j; i <= num; i++)
			cin >> result[j][i];
	back_tracking(1);
	system("pause");
	return 0;
}