[알고리즘] 백준 1248 맞춰봐 / python, 백트랙킹

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

1248번: 맞춰봐

 

✔ 풀이과정

첫째 줄에 수열의 크기 N이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문자는 두 번째 줄에 해당한다.

예제에서 첫번째줄 : -+0+ / 두번째줄 : +++ / 세번째줄 : -- / 네번째줄:+ 이다.

A = [-2, 5, -3, 1]일 때,

부호의 뜻은 첫번째줄 : A[0], A[0]+A[1], A[0]+A[1]+A[2], A[0]+A[1]+A[2]+A[3] / 두번째줄 : A[1], A[1]+A[2], A[1]+A[2]+A[3] .... 으로 합의 부호를 나타낸 것이다.

행렬 S를 이렇게 그릴 수 있다. 여기서 S[0][0], S[1][1], S[2][2], S[3][3]은 -2, 5, -3, 1의 부호와 일치한다는것을 알수있다. 이걸 이용해 탐색시간을 줄인다. S[index][index]가 '+'일 경우 1~10을 탐색, '-'일 경우 -10~-1을 탐색한다. 

 

S에 있는 부호들의 의미는 A의 인덱스3의 합, 인덱스 3 2의 합, 인덱스 3 2 1의 합, 인덱스 3 2 1 0의 합의 부호이다.

이게 인덱스 N이 만족해야하는 조건이다.

알아낸 규칙을 바탕으로 함수를 짜보자.

solve함수는 S의 대각선값이 0일때와 0이 아닐때로 나눠서 생각한다.

S[index][index]가 0이라면 구해야 하는 배열의 index값이 0이라는 뜻이니 0을 넣고 다음 인덱스의 함수를 부른다.

S[index][index]값이 0이 아니라면 양, 음에 따라 1~10, -10~-1 범위의 숫자를 조사한다. ck함수로 S의 부호들에 맞는 값인지 확인한다.

 

#부호와 합이 일치하는지 확인하는 함수
def ck(idx):
    hap = 0
    for i in range(idx, -1, -1):
        hap += result[i]
        if hap == 0 and S[i][idx] != 0:
            return False
        elif hap < 0 and S[i][idx] >= 0:
            return False
        elif hap > 0 and S[i][idx] <= 0:
            return False
    return True

def solve(idx):
    if idx == N:
        return True
    if S[idx][idx] == 0:
        result[idx] = 0
        return solve(idx+1)
    for i in range(1, 11):
        result[idx] = S[idx][idx] * i
        if ck(idx) and solve(idx+1):
            return True
    return False

N = int(input())
arr = list(input())
S = [[0]*N for i in range(N)]
for i in range(N):
    for j in range(i, N):
        temp = arr.pop(0)
        if temp == '+':
            S[i][j] = 1
        elif temp == '-':
            S[i][j] = -1

result = [0] * N
solve(0)
print(' '.join(map(str, result)))