[백준] 1248 Guess 🌟

문제

• $a_1, a_2, ..., a_n$ 배열이 주어질 때, S 행렬은 다음과 같이 계산할 수 있다.
  
  • 1 <= N <= 10
  • -10 <= $a_i$ <= 10
• $S_{ij}$ 는 $a_i + ... + a_j$ 이 0보다 크면 "+", 0보다 작으면 "-", 0이면 "0"이다.
• S 행렬이 주어질 때, 행렬 a를 찾아야 한다.
  • S 행렬은 각 행을 기준으로 N, N-1, ..., 1 개의 원소가 일렬로 주어진다.
  • 가능한 행렬 a의 경우의 수가 여러 개면 그 중 아무거나 출력해도 된다.

 

풀이

• 모든 경우의 수 확인하기 X (불가능)
  • -10 ~ 10 까지의 수가 N개 이므로 $O(21^N)$ 이므로 시간초과
• 백트래킹으로 경우의 수를 줄여야 한다.
  • s[i][i] 는 a[i] 부호와 같다.
  • a[1]~a[k]까지 확인했다고 할 때, a[k+1]는 부호에 대한 양수/음수 값만 확인하면 된다.
  • a[i] ~ a[k] 까지 합과 s[i][k+1] 부호로 a[k+1] 이 가능한 수인지 확인할 수 있다.
• a[k] 를 확정짓기 위해서는 다음 3가지 경우의 수가 있다.
  • 1. s[k][k] 가 0이면 0으로 확정 가능! 
  • 2. s[k][k] 가 양수(+)이면, a[k] 범위는 1~10 이 된다.
    • 1~10 각각의 경우에 a[i] ~ a[k] 합과 s[i][k+1] 부호로 가능한 경우의 수인지 확인한다.
  • 3. s[k][k] 가 음수(-)이면, a[k] 범위는 -1 ~ -10 이 된다.
    • 마찬가지로 각 경우에 대해 가능한 경우의 수인지 확인한다.

 

# 가능한 경우의 수인지 확인
def check(idx):
    sum = 0         
    for i in range(idx, -1, -1):
        sum += numbers[i]   # idx ~ 누적합
        # 누적합과 부호가 다르면 불가능한 경우
        if sum == 0 and s[i][idx] != 0:
            return False
        elif sum < 0 and s[i][idx] >= 0:
            return False
        elif sum > 0 and s[i][idx] <= 0 :
            return False
    return True

# 백트래킹
def solve(idx):
    if idx == N :           # 모든 숫자 확인한 경우 끝!
        return True
    if s[idx][idx] == 0 :   # 대각선 부호가 0이면 0으로 확정
        numbers[idx] = 0
        # idx+1 번 이후까지 가능한지 확인
        return solve(idx+1) 
    # 현재 인덱스 부호에 맞는 숫자 1~10 까지 넣으면서 확인
    for i in range(1, 11):
        numbers[idx] = s[idx][idx] * i
        if check(idx) and solve(idx+1) :
            return True
    return False

# 입력 받기
N = int(input())                # 행렬 a 원소개수
op_list = list(input())         # 부호 리스트
s = [[0]*N for _ in range(N)]   # S 행렬
# 부호를 숫자로 변환
for i in range(N-1, -1, -1):
    for j in range(N-1, i-1, -1):
        op = op_list.pop()
        if op == "+" :
            s[i][j] = 1
        elif op == "-":
            s[i][j] = -1        

numbers = [0] * N           # 반환할 숫자 배열

solve(0)
print(*numbers)

 

References

• 백준 1248번
• 2023.04.25 오늘의 문제