[백준] 1248번 맞춰봐 (by Python)

 

문제

https://www.acmicpc.net/problem/1248

1248번: 맞춰봐

 

풀이

def backtrack(k, stack):
    temp = k
    candidates = range(-10, 11)
    for i in range(k + 1):
        now = a[temp]
        if now == '+':
            candidates = [c for c in candidates if (sum(stack[i:k]) + c) > 0]
        elif now == '-':
            candidates = [c for c in candidates if (sum(stack[i:k]) + c) < 0]
        else:
            candidates = [c for c in candidates if (sum(stack[i:k]) + c) == 0]
        temp += (n - (i + 1))
    if k == (n - 1) and candidates:
        global ans
        stack[-1] = candidates[0]
        ans = stack
    else:
        for c in candidates:
            if not ans:
                stack[k] = c
                backtrack(k + 1, stack)


n = int(input())
a = input()
ans = []

backtrack(0, [0 for _ in range(n)])
print(*ans)

백트래킹 방법을 사용해 숫자를 매번 늘릴 때마다 지금까지의 조건과 맞는 후보군을 추려내어 그 안에서 DFS를 진행했다. 그리고 문제의 조건에 맞게 하나를 발견했으면 더이상 진행하지 않도록 했다.

설명이 너무 장황하고 쓸데없는 부분이 많아 짜증나는 문제였지만, 백트래킹 구현 과정에서 고민해볼 거리가 많았던 문제.