BOJ 1248

17 Apr 2020 • ProblemSolving

맞춰봐

문제출처

문제 해석

  • 수열의 크기 N과 문자열 S가 주어졌을 때, 만족하는 크기 N의 수열을 출력하는 문제입니다.
  • 문자열 S(크기: (Nx(N+1)/2))는 i~j까지의 부분합이 0인지, 0보다 큰지, 0보다 작은지 나타냅니다.

설계(10)

  • 약간의 아이디어가 필요한 백트래킹 문제입니다.
  • 예제를 예시로 설명하자면, 문자열 S =”-+0++++-+”에서 1~4번째는 수열의 첫번째부터 4번째까지 차례대로 더했을 때의 값의 변화를 나타냅니다.
  • 다음 5~7번째는 2~4번째 수열의 누적합의 변화입니다.
  • 이렇게 따라가다 보면 마지막에 남는 문자는 4번째 수열의 숫자의 누적합의 변화가 됩니다. 연산에 따라서 해당 인덱스의 숫자가 어떤것이 나올 지 범위를 알 수 있게 됩니다.
  • 이렇듯, 첫번째 문자열부터 탐색하지 않고, 마지막 인덱스의 문자에 따라서 N번째 수열 숫자를 정한 후, 백트래킹을 하는 방식으로 구현하면 됩니다.
  • 여러가지 답이 나올 수 있기 때문에 possible변수를 이용하여 원하는 수열을 찾으면 해당 수열을 출력한 후, 즉시 리턴하도록 합니다.

구현(15)

코드
#include <iostream>
using namespace std;
#define MAXN 10

int num[MAXN];
string S;
int N;
bool possible;
void backtrack(int start, int end, int len){
    if (possible) return;
    if (len > N){
        possible= true;
        for (int i = 0;i< N; i++){
            cout << num[i] <<" ";
        }
        return;
    }
    if (start == end){
        int idx = N-len;
        if (S[start] == '+'){
            for (int i = 1; i <=10; i++){
                num[idx] = i;
                backtrack(start-(len+1),start-1,len+1);
            }
        }
        else if (S[start] == '-'){
            for (int i = -1; i>=-10; i--){
                num[idx] = i;
                backtrack(start-(len+1),start-1,len+1);
            }
        }
        else{
            backtrack(start-(len+1),start-1,len+1);
        }
    }
    else{
        if (S[start]=='+'){
            for (int i = 1; i <= 10; i++){
                int idx = N-len+1;
                int sum = i;
                bool flag = false;
                for (int j = start+1; j<=end; j++){
                    sum +=num[idx];
                    if (S[j]=='+'){
                        if (sum<=0) {
                            flag=true;
                            break;
                        }
                    }
                    else if (S[j] =='-'){
                        if (sum >=0){
                            flag = true;
                            break;
                        }
                    }
                    else{
                        if (sum!=0){
                            flag = true;
                            break;
                        }
                    }
                    idx++;
                }
                if (!flag){
                    num[N-len] = i;
                    backtrack(start-(len+1),start-1,len+1);
                }
            }
        }
        else if (S[start] == '-'){
            for (int i = -1; i >= -10; i--){
                int idx = N-len+1;
                int sum = i;
                bool flag = false;
                for (int j = start+1; j<=end; j++){
                    sum +=num[idx];
                    if (S[j]=='+'){
                        if (sum<=0) {
                            flag=true;
                            break;
                        }
                    }
                    else if (S[j] =='-'){
                        if (sum >=0){
                            flag = true;
                            break;
                        }
                    }
                    else{
                        if (sum!=0){
                            flag = true;
                            break;
                        }
                    }
                    idx++;
                }
                if (!flag){
                    num[N-len] = i;
                    backtrack(start-(len+1),start-1,len+1);
                }
            }
        }
        else{
            int sum = 0;
            bool flag = false;
            int idx = N-len+1;
            for (int j = start+1; j<=end; j++){
                sum +=num[idx];
                if (S[j]=='+'){
                    if (sum<=0) {
                        flag=true;
                        break;
                    }
                }
                else if (S[j] =='-'){
                    if (sum >=0){
                        flag = true;
                        break;
                    }
                }
                else{
                    if (sum!=0){
                        flag = true;
                        break;
                    }
                }
                idx++;
            }
            if (!flag){
                backtrack(start-(len+1),start-1,len+1);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> S;
    backtrack(S.length()-1,S.length()-1,1);
    return 0;
}
디버깅
제출결과
  • 12 ms

마무리

  • 마지막 인덱스의 수열부터 차례대로 찾아나가는 아이디어가 필요한 백트래킹 문제였습니다.
 BOJ

Related Posts