백준 1248 - Guess

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

1248번: Guess

 

 

풀이

1. 기본적으로 재귀를 이용한다. dfs(index + 1)을 계속 호출하면서 answer가 s 배열을 만족하는지 check 함수를 통해 확인한다.

2. 문제에서 중요한 힌트는 바로 answer[index]의 부호는 반드시 s[index][index]라는 것이다. 따라서, 재귀 호출 중 s[index][index]가 0이라면 answer[index]에 0을 넣고 다음 단계 dfs(index + 1)로 이동한다.

3. s[index][index]가 0이 아닌 경우, s가 +1 이라면 1 ~ 10, s가 -1이라면 -1 ~ -10을 answer에 넣어보면서 answer가 s 배열을 만족하는지 check 함수를 통해 확인하고, 다음 단계 dfs(index + 1)을 호출한다.

 

n = int(input())
data = input()
k = 0
s = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(i, n):
        if data[k] == '0':
            s[i][j] = 0
        elif data[k] == '-':
            s[i][j] = -1
        else:
            s[i][j] = 1
        k += 1


def check(index):
    total = 0
    for i in range(index, -1, -1):
        total += answer[i]
        if total == 0 and s[i][index] != 0:
            return False
        elif total < 0 and s[i][index] != -1:
            return False
        elif total > 0 and s[i][index] != 1:
            return False
    return True


def dfs(index):
    if index == n:
        return True

    if s[index][index] == 0:
        answer[index] = 0
        return dfs(index + 1)

    for i in range(1, 11):
        answer[index] = s[index][index] * i
        if check(index) and dfs(index + 1):
            return True
            
    return False


answer = [0] * n
dfs(0)
print(' '.join(map(str, answer)))