[Python/파이썬] 백준 1248번 Guess

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

코드

n = int(input())
input_data = "_"+input()

sign_sequence = [[None]*(n+1) for _ in range(n+1)]
idx = 1
for i in range(1, n+1):
    for j in range(i, n+1):
        sign_sequence[i][j] = input_data[idx]
        idx += 1


def bt(idx, arr, acc):
    if idx == n+1:
        print(*arr[1:])
        exit()
    for new_num in range(-10, 11):
        new_acc = acc[-1]+new_num
        is_possible = True
        for left in range(1, idx+1):
            section_sum = new_acc-acc[left-1]
            if section_sum == 0 and sign_sequence[left][idx] != "0":
                is_possible = False
                break
            if section_sum > 0 and sign_sequence[left][idx] != "+":
                is_possible = False
                break
            if section_sum < 0 and sign_sequence[left][idx] != "-":
                is_possible = False
                break
        if is_possible:
            bt(idx+1, arr+[new_num], acc+[new_acc])


bt(1, [0], [0])

 

N이 10개 이하로 고정되어 있고, 배열에 나올 수 있는 숫자의 범위도 -10 이상 10 이하라서 모든 케이스를 다 해보도록 했다. 물론 모든 경우 다 하면 너무 오래걸리니까 절대 안되는 경우는 가지치기 해준다.

 

풀이 방법 자체는 금방 찾았는데 가지치기 조건 설정 잘못해서 왜 안되지...왜 안되지...이러느라 시간이 좀 걸렸다....