[Python / BOJ 1248] Guess

 

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

 

 

 

0. 문제

 

어떤 sequence가 주어지면 sign matrix 를 정의할 수 있다.

예를 들어 (a1, a2, a3, a4) = ( −1, 5, −4, 2) 가 주어지면 sign matrix는 다음과 같다.

 

sign matrix

sign matrix가 주어졌을 때 만족하는 sequence 를 구하여라. sequence 값은 -10 ~ 10까지 가능하다.

 

 

 

 

 

1. 아이디어

길이 N 짜리 sequence는 길이 N-1 짜리 sequence에 숫자 하나 더 붙인 것이다.

즉, 길이 1부터 N까지 하나씩 숫자를 붙여가며 sign matrix 를 만족하는지 확인하면 된다.

 

예를 들어 3x3 sign matrix를 만족하는 sequence (a1, a2, a3) 를 구했다고 하자.

그럼 길이 4인 sequence를 구하기 위해서는 다음을 따른다.

• a4는 (4, 4) 에 있는 부호를 따른다. - 면 -10 ~ -1이고, +면 1~10이고, 0이면 0이다.
• a4를 추가하면 column 4를 만족하는지만 확인하면 된다.
• 왜냐면, 길이 3인 sequence는 이미 3x3 sign matrix를 만족하기 때문이다. 이 부분을 구현한 것이 아래 구현에서 check 함수이다.

 

 

 

2. 구현

# arr의 마지막 idx (check_idx) 값이 적절한지 확인
def check(arr):
    check_idx = len(arr) - 1
    for i in range(len(arr)):
        value = sum(arr[i:])
        if value > 0 and matrix[i][check_idx] != '+':
            return False
        elif value < 0 and matrix[i][check_idx] != '-':
            return False
        elif value == 0 and matrix[i][check_idx] != '0':
            return False
    return True


def func(result):
    # 종료 조건 => 길이 N이면 종료
    if len(result) >= N:
        print(*result)
        exit()

    # 재귀 => idx 번째의 번호 정하기 | matrix[idx][idx]는 해당 숫자만 덧셈임
    idx = len(result)
    if matrix[idx][idx] == '+':
        seq_range = range(1, 11)
    elif matrix[idx][idx] == '-':
        seq_range = range(-10, 0)
    else:
        seq_range = range(0, 1)
    # seq_range 범위 값을 하나씩 넣어보기
    for num in seq_range:
        if check(result + [num]):
            func(result + [num])


# 문제의 matrix 그리기
N = int(input())
matrix = [[0] * N for _ in range(N)]
IN = list(input())
for i in range(N):
    for j in range(i, N):
        matrix[i][j] = IN.pop(0)
# 함수
func([])