[백준] 1248번 Guess - Python / 알고리즘 기초 2/2 - 브루트 포스 - 재귀

ByungJik_Oh·2025년 4월 11일

[Baekjoon Online Judge]

목록 보기

98/244

💡 문제

정수 시퀀스 a $_1$ , a $_2$ , …, a $_n$ 이 주어졌을 때 , 1 ≤ i ≤ j ≤ n에 대해 a $_i$ + … + a $_j$ > 0이면 S $_{ij}$ ="+"가 되고, a $_i$ + … + a $_j$ < 0이면 S $_{ij}$ ="−"가 되고, 그렇지 않으면 S $_{ij}$ ="0"이 되도록 부호 행렬 S를 정의합니다.

예를 들어, (a $_1$ , a $_2$ , a $_3$ , a $_4$ )=(−1, 5, −4, 2)이면 부호 행렬 S는 4×4 행렬입니다.

수열 (−1, 5, −4, 2)는 부호 행렬을 생성한다고 합니다. 부호 행렬은 정수 수열로 생성될 수 있으면 유효합니다.

정수 시퀀스가 주어지면 그 부호 행렬을 쉽게 계산할 수 있습니다. 이 문제는 반대 방향에 관한 것입니다. 유효한 부호 행렬이 주어졌을 때, 그 부호 행렬을 생성하는 정수 시퀀스를 구하세요. 두 개 이상의 서로 다른 정수 시퀀스가 동일한 부호 행렬을 생성할 수 있습니다. 예를 들어, 시퀀스 (−2, 5, −3, 1)은 시퀀스 (−1, 5, −4, 2)와 동일한 부호 행렬을 생성합니다.

유효한 부호 행렬이 주어졌을 때, 해당 부호 행렬을 생성하는 정수 시퀀스를 찾는 프로그램을 작성하세요. 시퀀스의 모든 정수는 -10에서 10 사이(두 값 모두 포함)라고 가정할 수 있습니다.

입력

첫째 줄에는 정수 n(1 ≤ n ≤ 10)이 주어진다. 여기서 n은 정수열의 길이이다. 둘째 줄에는 n(n+1)/2개의 문자로 구성된 문자열이 주어진다. 처음 n개의 문자는 부호 행렬의 첫 번째 행에 대응하고, 그 다음 n-1개의 문자는 두 번째 행에 대응하고, ..., 마지막 문자는 n번째 행에 대응한다.

출력

부호 행렬을 생성하는 n개의 정수로 구성된 수열을 한 줄에 정확히 출력합니다. 부호 행렬을 생성하는 수열이 두 개 이상인 경우, 그 중 하나를 출력할 수 있습니다. 수열의 모든 정수는 -10에서 10 사이의 값이어야 합니다(두 값 모두 포함).

💭 접근

입력으로 주어진 n 길이의 순열을 뽑아 주어진 부호 행렬에 만족하는 순열을 출력한다.

먼저, 순열을 구성하는 정수의 범위가 -10~10 이기 때문에 탐색 범위를 0~10으로 줄이기 위해 부호 행렬을 '-'는 -1, '+'는 1, '0'은 0으로 구성해준다.

for i in range(n):
    for j in range(i, n):
        a = s.pop(0)
        if a == '+':
            op[i][j] = 1
        elif a == '-':
            op[i][j] = -1
        else:
            op[i][j] = 0

	1	2	3	4		1	2	3	4
1	-	+	0	+	->	-1	1	0	1
2		+	+	+	->		1	1	1
3			-	-	->			-1	-1
4				+	->				1

dfs 함수를 호출하여 순열을 구성하는데, op[0][0], op[1][1], ..., op[n][n] 은 n자리 수의 부호를 나타내므로 이 전에 저장한 부호 행렬의 수를 곱해서 사용해준다.

def dfs(depth):
    if depth == n:
        print(*ans)
        sys.exit()
    else:
        if op[depth][depth] == 0:
            if check(depth, 0):
                dfs(depth + 1)
        else:
            for i in range(1, 11):
                num = i * op[depth][depth]
                if check(depth, num):
                    dfs(depth + 1)

dfs 함수에서 순열을 구성할 때 한가지 확인해야하는 조건이 더 있다. 각 자리까지의 합이 부호 행렬의 부호와 일치하는지 확인해주고, 일치하지 않는다면 백트래킹을 통해 더 이상 탐색하지 않도록 한다.

def check(idx, num):
    ans[idx] = num
    sum = 0
    for i in range(idx, -1, -1):
        sum += ans[i]
        if op[i][idx] > 0 and sum <= 0:
            return False
        elif op[i][idx] < 0 and sum >= 0:
            return False
        elif op[i][idx] == 0 and sum != 0:
            return False
    return True

위와 같은 과정을 거쳐 주어진 순열의 길이를 만족하는 순열이 완성되면 출력하고 종료해준다. (하나의 수열만 출력하면 되므로)

 if depth == n:
        print(*ans)
        sys.exit()

📒 코드

import sys

def check(idx, num):
    ans[idx] = num
    sum = 0
    for i in range(idx, -1, -1):
        sum += ans[i]
        if op[i][idx] > 0 and sum <= 0:
            return False
        elif op[i][idx] < 0 and sum >= 0:
            return False
        elif op[i][idx] == 0 and sum != 0:
            return False
    return True

def dfs(depth):
    if depth == n:
        print(*ans)
        sys.exit()
    else:
        if op[depth][depth] == 0:
            if check(depth, 0):
                dfs(depth + 1)
        else:
            for i in range(1, 11):
                num = i * op[depth][depth]
                if check(depth, num):
                    dfs(depth + 1)

n = int(input())
s = list(input())

op = [[None for _ in range(n)] for _ in range(n)]
ans = [0 for _ in range(n)]

for i in range(n):
    for j in range(i, n):
        a = s.pop(0)
        if a == '+':
            op[i][j] = 1
        elif a == '-':
            op[i][j] = -1
        else:
            op[i][j] = 0

dfs(0)