[백준] Guess

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

1248번: Guess

 

1. 문제 이해

수열이 주어지고 i ~ j 범위내에 있는 숫자들을 더했을 때 양수이면 '+', 음수이면 '-', 0이면 '0'이 적혀있는 행렬이 주어집니다. 해당 행렬은 만족하는 수열중 아무거나 구하면 됩니다. 단, 숫자들은 -10 ~ 10 범위 내에 있는 숫자들로 이루어져있습니다.

2. 문제 접근

첫번째 접근: 위상정렬(?)

숫자들의 부호는 알 수 있으므로 숫자간의 절대값의 대소를 비교하여 위상정렬을 통해 숫자를 주려고 했는데 숫자간의 대소를 비교하는 방법을 찾지 못했고 두 숫자를 합했을 때 0이 되는 경우 대소를 통한 단방향 그래프를 만들 수 없어 포기하였습니다.

 

두번째 접근: 백트래킹

N의 사이즈가 10이고 가능한 숫자의 범위가 20이라서 백트래킹을 통해 풀 수 있을 것 같다고 생각했습니다. 개인적으로 백트래킹은 시간복잡도가 예측이 잘되지 않아서 N의 범위가 크지 않을 때 시도해봅니다. 각각 숫자의 부호를 알고 있으므로 음수면 -10 ~ -1, 양수면 1 ~ 10, 0이면 0이므로 범위 내에 있는 숫자를 넣어보고 행렬 조건을 만족하는지 체크하여 가지치기를 해주었습니다.

3. 풀이

import sys

sys.stdin = open("input.txt")

input = sys.stdin.readline

n = int(input())

status = [
    [0] * n
    for _ in range(n)
]

relation = list(input().rstrip())
idx = 0
for i in range(n):
    for j in range(i, n):
        r = relation[idx]
        idx += 1

        if r == '+':
            status[i][j] = 1
        elif r == '-':
            status[i][j] = -1

nums = [0] * n
isEnd = False

def check(cnt):
    end = cnt
    sum_of_num = 0

    for start in range(end, -1, -1):

        sum_of_num += nums[start]

        # 0이 아닌 경우
        if status[start][end] == 0 and sum_of_num != 0:
            return False

        if status[start][end] != 0 and sum_of_num == 0:
            return False

        #부호가 다르면 만족하지 못한다.
        if status[start][end] * sum_of_num < 0:
            return False

    return True


def backTracking(cnt):
    global isEnd
    # 끝난 경우
    if isEnd:
        return
    # 행렬 조건을 만족하지 못한 경우
    if not check(cnt - 1):
        return

    if cnt == n:
        print(*nums)
        isEnd = True
        return

    # 현재 숫자가 양수인 경우
    if status[cnt][cnt] > 0:
        for i in range(1, 11):
            nums[cnt] = i
            backTracking(cnt + 1)

    # 현재 숫자가 음수인 경우
    elif status[cnt][cnt] < 0:
        for i in range(-10, 0):
            nums[cnt] = i
            backTracking(cnt + 1)
    # 현재 숫자가 0인 경우
    else:
        nums[cnt] = 0
        backTracking(cnt + 1)

backTracking(0)

4. 회고

백트래킹을 어느정도 생각은 했으나 시간복잡도 예상이 잘 가지 않아서 시도해보지 않았는데 백트래킹으로 푸니 맞았습니다. N이 10정도이고 매 단계마다 가지치기가 가능하면 백트래킹으로 풀이가 가능하다는 것을 알 수 있었습니다.