[1248] 맞춰봐

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<set>
#include<cstdlib>
#include<sstream>
using namespace std;

char a[100][100];
int p[1001];
int n;

int checkarray[11];;
long  long real = 100000000;
vector <int> temp;
vector<vector<int>> all;
bool check() {
	bool flag = true;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = i; j < n; j++) {
			sum += temp[j];
			if (a[i][j] == '-') {
				if (sum >= 0) return false;
			}
			else if (a[i][j] == '+') {
				if (sum <= 0) return false;
			}
			else {
				if (sum != 0) return false;
			}
		}
	}
	return flag;
}
bool good(int cnt , int num) {
	temp[cnt] = num;
	bool flag = true;
	for (int i = 0; i <= cnt; i++) {
		int sum = 0;
		for (int j = i; j <=cnt; j++) {
			sum += temp[j];
			if (a[i][j] == '-') {
				if (sum >= 0) return false;
			}
			else if (a[i][j] == '+') {
				if (sum <= 0) return false;
			}
			else {
				if (sum != 0) return false;
			}
		}
	}
	return flag;
};
bool solve(int cnt) {
	if (cnt == n) {
		if (check()) {
			return true;
		}
		else return false;
	}
	if (cnt >= n) return false;

	if (a[cnt][cnt] == '+') {
		for (int i = 1; i <= 10; i++) {
			if (good(cnt,i) == false) continue;
			temp[cnt] = i;
			if (solve(cnt + 1)) return true;
		}
	}
	else if (a[cnt][cnt] == '-') {
		for (int i = -10; i <= -1; i++) {
			if (good(cnt, i) == false) continue;
			temp[cnt] = i;
			if (solve(cnt + 1)) return true;
		}
	}
	else if (a[cnt][cnt] == '0') {
			temp[cnt] = 0;
			if (solve(cnt + 1)) return true;
	}
	return false;
};
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			cin >> a[i][j];
		}
	}
	temp.resize(n);

	if (solve(0)) {
		for (int i = 0; i < n; i++) {
			cout << temp[i] << ' ';
		}
		cout << '\n';
	}
	

	return 0;
}

1. 처음 : -10 ~ 10 까지 모든 수를 조합해서 수를 계산하면, 21^10 이 되어 시간 초과 발생한다.
   2: 따라서 부호를 나눠봤는데 a[i][j]가 i==j 일때는 temp[i] 와 a[i][j] 의 부호가 같다. 따라서 경우를 나눠주면 +, - ,0 으로 10^10 으로 줄어든다. 하지만 이마저도 시간 초과 발생.
   3: 따라서 temp 가 들어갈때마다 check 를 해줘야 한다. good 함수를 만들어서 이를 체크해줬다.

주의 !! a[i][j] == '0'으로 해야함....a[i][j]== 0으로 조건문 구성해서 해멤.. ㅋㅋ