백준 1248 / 맞춰봐

문제 설명에 온갖 말장난을 쳐놔서 이해하는데 오랜 시간이 걸렸다.

요약하자면, -10~10, 총 21개의 수로 입력받은 결과를 만족하는 n개의 수를 찾는 문제.

중복이 가능하기 떄문에 총 21^n개의 경우의수가 발생한다. (n=10일 경우 시간초과가 무조건 발생한다)

그렇기에 몇몇 체크를 추가하여 걸리는 시간을 줄여야 한다.

여기서 관찰력과 아이디어가 필요한데,

입력받은 부호(-,0,+)중 S[i][i]는 i의 부호를 말하고 있다는 점이다.

그러나 이 점을 활용하여 코드를 구성해도 시간초과가 걸린다.

여기서 또 하나 체크를 추가해주어야한다.

정답 배열 ans에 담긴 숫자가 n이 될때마다 체크를 하지말고,

숫자가 담길떄 마다 체크를 실행하는 것이다.

이런 자잘한 아이디어를 생각해내기 힘들기 떄문에 굉장히 어려운 문제이다.

코드

#include<stdio.h>
#include<vector>
#include<queue>
#include<iostream>
 
using namespace std;
 
 
int buho[10][10];
 
vector<int>ans;
 
int n;
 
bool check(int index) {
    int sum = 0;
    for (int i = index; i >= 0; i--) {
        sum += ans[i];
        if (buho[i][index] == 0) {
            if (sum != 0)return false;
        }
        if (buho[i][index] < 0) {
            if (sum >= 0)return false;
        }
        if (buho[i][index] > 0) {
            if (sum <= 0)return false;
        }
 
    }
    return true;
}
 
bool go(int index) {
    if (index == n) {
        return true;
    }
    if (buho[index][index] == 0) {
        ans[index] = 0;
        return check(index) && go(index + 1);
    }
 
    for (int i = 1; i <= 10; i++) {
        ans[index] = buho[index][index] * i;
        if (check(index) && go(index + 1))
            return true;
 
    }
 
    return false;
}
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> n;
    ans.resize(n);
 
 
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            char c;
            cin >> c;
            if (c == '0') {
                buho[i][j] = 0;
            }
            if (c == '+') {
                buho[i][j] = 1;
            }
            if (c == '-') {
                buho[i][j]=-1;
            }
 
        }
    }
 
    go(0);
    
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    
}