BOJ 1248 · 맞춰봐

알고리즘 분류 : 백트래킹  

입력으로 주어지는 합의 부호에 맞는 숫자 배열을 출력하는 문제다. 총 21개의 숫자 중에서 N개의 숫자를 골라야 한다. 일반적인 재귀 함수를 통해 브루트 포스로 구현하면 시간 초과가 나기 쉬우므로, 백트래킹 기법을 사용해야 한다.

• 숫자의 범위 (-10 ~ 10) 만큼 재귀 함수를 호출한다.
• 하나의 숫자를 고를 때마다, 이 숫자가 주어진 부호에 맞는지 확인한다.
• 해당 숫자가 가능하다면, 다음 재귀 함수를 호출한다.
• 하나의 숫자 리스트만 찾으면 되므로, 찾으면 바로 프로그램을 종료한다.

---

C++ 소스코드

#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int n;
char a[10][10];
vector<int> v;

bool possible(int idx) {
    int sum = 0;
    for (int i=idx; i>=0; i--) {
        sum += v[i];
        if (a[i][idx] == '+' && sum <= 0) return false;
        if (a[i][idx] == '0' && sum != 0) return false;
        if (a[i][idx] == '-' && sum >= 0) return false;
    }
    return true;
}

void solve(int idx) {
    if (idx == n) {
        for (auto k : v) printf("%d ", k);
        printf("\n");
        exit(0);
    }
    for (int i=-10; i<11; i++) {
        v.push_back(i);
        if (possible(idx)) solve(idx+1);
        v.pop_back();
    }
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        for (int j=i; j<n; j++) {
            scanf(" %1c", &a[i][j]);
        }
    }
    solve(0);
    return 0;
}

---

PyPy3 소스코드

n = int(input())
a = [[0]*n for _ in range(n)]
b = list(input())
v, k = [], 0

def possible(idx):
    s = 0
    for i in range(idx, -1, -1):
        s += v[i]
        if a[i][idx] == '+' and s <= 0:
            return False
        if a[i][idx] == '0' and s != 0:
            return False
        if a[i][idx] == '-' and s >= 0:
            return False
    return True

def solve(idx):
    if idx == n:
        print(' '.join(map(str, v)))
        exit(0)
    for i in range(-10, 11):
        v.append(i)
        if possible(idx):
            solve(idx+1)
        v.pop()

for i in range(n):
    for j in range(i, n):
        a[i][j] = b[k]
        k += 1
solve(0)

✓ Python 3로 제출하면 시간 초과가 나와서, PyPy3로 제출했다. 개선이 필요한 알고리즘이다.

---

참고

• 백준 온라인 저지 : BOJ 1248