[백준] 1248 - Guess (G3)

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

어떤 수열의 연속하는 모든 부분수열 ai ~ aj 에 대한 합의 부호값 (+, 0, -) 를 알고 있을 때, -10 ~ 10 사이의 숫자를 사용하여 만들 수 있는 수열을 찾는 문제

 

처음에는 어떻게 해야할 지 감이 안왔는데, 보통 이렇게 알고리즘이 감이 안오는 문제는 입력 크기를 줄이고 완전탐색으로 풀도록 유도하는 경우가 많다.

 

이 문제도 수열의 길이가 최대 10으로 -10 ~ 10 까지 숫자 10개를 모두 시도해보면서 풀 수 있다.

그렇다고 정말 나이브하게 완탐으로가면 21^10 이라는 경우의 수를 체크해야 한다.

하지만 모든 부분수열의 ai ~ aj 부호값을 모두 만족해야 하는점에서 경우의 수를 치다보면 체크할 경우의 수가 확 줄어든다는 것을 알 수 있다.

 

결론적으로 이 문제는 백트래킹으로 풀 수 있는 문제이다.

백준의 n과 m 문제를 풀듯이 수열에 -10부터 10까지 숫자를 하나씩 넣어보면서 지금까지 만든 수열이 부분 수열에 대한 합의 부호값을 만족하는지 체크하고, 체크한다면 이 수열 뒤에 -10 ~ 10을 모두 넣어보면서 경우의 수를 체크할 수 있다.

 

n = int(input())
s = input()
matrix = [["." for _ in range(n)] for _ in range(n)]
k = 0
for i in range(n):
    for j in range(i, n):
        matrix[i][j] = s[k]
        k += 1

def check(nums):
    for i in range(len(nums)):
        s = sum(nums[i:])
        now_cell = matrix[i][len(nums)-1]
        if s > 0 and now_cell != '+':
            return False
        if s == 0 and now_cell != '0':
            return False
        if s < 0 and now_cell != '-':
            return False

    return True


def f(nums):
    if not check(nums):
        return

    if len(nums) == n:
        print(*nums)
        exit(0)

    for i in range(-10, 11):
        f(nums + (i,))

f(tuple())