백준 1248 맞춰봐 쉬운 풀이 (C++/CPP)

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

문제 추상화

• 숫자 갯수와, 각 구간합이 주어졌을때, 각 숫자 구하기

아이디어

• 백트래킹으로 일일히 구하는 것이 가능할까?

  • A는 -10~10 > 21개
  • 21 ^ 10 가 일치해야함 > 너무큼
  • 다른방법이 있나?
    • 가지치기로 백트래킹 시간복잡도가 줄어들것 같긴한데...
    • 일단 해보자

시간복잡도 계산

• 21^10

인트 계산

• 숫자 범위 정해져있음 > INT 가능

코드

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
 
using namespace std;
 
vector<int> v;
int N;
string s;
char ec[15][15];
 
bool chk() {
    int cnt=0;
    for(int j=0; j<v.size(); j++) {
        for(int i=j; i<v.size(); i++) {
//            int idx = N * j + i;
            int sumv = accumulate(v.begin()+j , v.begin()+i+1,0);
            if(ec[j][i] == '-') {
                if( sumv>=0) return false;
            }else if(ec[j][i] == '0') {
                if(sumv !=0)return false;
            } else {
                if(sumv <= 0) return false;;
            }
            cnt++;
        }
    }
    
    return true;
}
 
void dfs() {
    if(v.size() == N) {
        for(int x : v) {
            cout << x << ' ';
        }
        exit(0);
        return;
    }
    
    // 전에 합한 수에따라 값을 올려줘서 시작
    
    
    for(int i=-10; i<=10; i++) {
        v.push_back(i);
        if(chk()==1) dfs();
        v.pop_back();
    }
}
 
int main() {
    cin >> N >> s;
    int cnt=0;
    for(int j=0; j<N; j++) {
        for(int i=j; i<N; i++) {
            ec[j][i] = s[cnt++];
        }
    }
    
    dfs();
    
    
    return 0;
}
 
 

문제유형

• 백트래킹