악곱 == 악성곱슬

백트래킹

---

이 문제는 백트래킹을 사용하여 구간합의 부호를 보고 숫자 배열을 역으로 맞추는 문제이다.

index 는 +, -, 0 의 부호를 2차원 배열로 바꾼 배열이고,

check 는 구간합과 부호가 일치하는지 검사하는 것이다.

이 문제에서 프루닝을 적용할 수 있는 부분은, 부호가 다를 때 더이상 볼 필요 없다는 점과, 이미 답이 나왔다면 더이상 탐색을 하지 않아도 된다는 점이다. 나머지는 구현 능력이므로 간단하게 알고리즘만 소개하겠다.

1. 인덱스 리스트 구함(부호를 2차원 배열(행렬꼴)로 접근하기 용이하게 바꿈)
2. 백트래킹을 수행 → max_depth는 N과 동일하도록, summation 값은 들고다니며 연산을 최소화 한다.
3. 만약 체크에서 통과하지 못했으면 아래 가지는 더이상 보지 않는다.
4. 만약 이미 최대치까지 갔다면 결과가 나왔다는 것이고 더이상 탐색할 이유가없다. 아예 프로그램을 종료한다.

구현

---

import sys

def check(summation, array):
    cur = summation
    row = len(array) - 1
    for i in range(len(index[row])):
        if index[row][i] == "+" and cur <= 0:
            return False
        if index[row][i] == "-" and cur >= 0:
            return False
        if index[row][i] == "0" and cur != 0:
            return False
        cur -= array[i]
    return True

def backtrack(answer, depth, max_depth, summation):
    if not check(summation, answer):
        return False

    if depth == max_depth-1:
        print(*answer)
        return True

    for value in numbers:
        answer.append(value)
        summation += value
        if backtrack(answer, depth+1, max_depth, summation):
            return True
        summation -= value
        answer.pop()
    return False

def solution(n):
    answer = []
    summation = 0
    for value in numbers:
        answer.append(value)
        summation += value
        if backtrack(answer, 0, n, summation):
            return True
        summation -= value
        answer.pop()

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    seq = list(sys.stdin.readline().rstrip())
    numbers = [Num for Num in range(-10, 11)]
    index = [[] for _ in range(N)]
    idx = 0
    for i in range(N):
        for j in range(i, N):
            index[j].append(seq[idx])
            idx += 1
    solution(N)