[BOJ] 1248 : 맞춰봐

1248 : 맞춰봐

풀이

백트래킹

숫자 n개가 주어질때 0,-,+ 부호를 보고 각숫자가 어떤 숫자가 될 수 있는지 맞히는 문제이다.

각 부호는 행렬의 우삼각행렬에서 부분합을 뜻한다.

0 1 2 3 4

1 * x y z

2 - * y z

3 - - * z

4 - - - *

이때 첫번째 포인트는 i==j인곳(*표시)는 A[i]가 된다는 점이다.

그것만 가지고 가능한 경우를 모두 탐색하고, x==n이 되었을때 종료시키면 시간초과가 뜬다.

그래서 두번째 포인트!

마지막에 올바른지 판단하지 않고 각 숫자를 넣어봤을때 바로바로 중간점검을 할 수있게 바꿨다.

즉 x가3일때(3번째 x를 탐색할떄) 탐색에 앞서서 ans[0]과 ans[1]의 합의 부호가

위 그림의 ‘x’가 맞는지 살폈다.

그리고 x가4일때 탐색에 앞서서 위 그림의 ‘y’들이 올바른 부호인지 살폈다.

코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

char arr[10][10];
vector<int> ans;
int n;
int flag = 0;
void go(int x) {
    if (flag)
        return;
    //전에 넣은숫자를 중간점검
    int sum = 0;
    for (int j = 0; j < x; j++) {
        sum += ans[j];
    }
    for (int j = 0; j < x-1; j++) {
        if (arr[j][x-1] == '0') {
            if (sum != 0)
                return;
        }
        else if (arr[j][x - 1] == '+') {
            if (sum <= 0)
                return;
        }
        else if (arr[j][x - 1] == '-') {
            if (sum >= 0)
                return;
        }
        sum -= ans[j];
    }

    if (x == n) {
        //정답찾음
        flag = 1;
        for (int x : ans) {
            cout << x << ' ';
        }
        return;
    }

    if (arr[x][x] == '0') {
        ans.push_back(0);
        go(x + 1);
        ans.pop_back();
    }
    else if (arr[x][x] == '+') {
        for (int i = 1; i <= 10; i++) {
            ans.push_back(i);
            go(x + 1);
            ans.pop_back();
        }
    }
    else {
        for (int i = -10; i <= -1; i++) {
            ans.push_back(i);
            go(x + 1);
            ans.pop_back();
        }
    }
}

int main() {
    cin >> n;
    char trash;
    scanf("%1c", &trash);
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            scanf("%1c", &arr[i][j]);
        }
    }
    go(0);
    return 0;
}

Written on April 8, 2019