[백준] 1248 맞춰봐

 

백트래킹을 이용해 풀 수 있는 문제다!

근데 막풀면 틀린다 

처음에 그냥 있는그대로 넣고 구하고 생각해보니 시간이 20^10이였다 ㅋㅋㅋ

 

구간의합의 부호를 주기 때문에

수를 고르고 구간의 합을 확인 후 가능하면 넘기면 된다!

 

근데 헷갈리는 부분은 같은 수를 중복으로 못쓰는 줄 알았는데

사용가능하다..!

 

중복으로 사용 못하게 풀면 틀린다!

 

소스코드

#include <iostream>
using namespace std;
 
int n;
char op[12][12];
int psum[12],ans[12];
 
bool check(int pos){
    for(int i=1;i<=pos;i++){
        char o = op[i][pos];
        int sum = psum[pos] - psum[i-1];
        if(o=='+' && sum<=0) return false;
        if(o=='-' && sum>=0) return false;
        if(o=='0' && sum!=0) return false;
    }
    return true;
}
 
void solve(int pos){
    if(pos==n+1){
        for(int i=1;i<=n;i++) printf("%d ",ans[i]);
        exit(0);
    }
 
    for(int i=0;i<=20;i++){
        ans[pos] = i-10;
        psum[pos] = psum[pos-1] + ans[pos];
        if(check(pos)) solve(pos+1);
        ans[pos]=psum[pos]=0;
    }
}
 
int main(){
    scanf(" %d",&n);
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            scanf(" %1c",&op[i][j]);
        }
    }
    solve(1);
}