[BOJ] 2529. 부등호

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

2529번: 부등호

 

 

1. 해결방법

완전탐색 백트래킹을 이용하여 문제를 해결하였다.
아이디어는 쉽지만 코드로 옮기는 과정에서 3시간 정도 잡아 먹은 것 같다.. 역시 아직 알고리즘을 더 해야겠다.

각 숫자 0 ~ 9는 하나만 들어가야 하므로, 방문 여부 체크는 반드시 해주어야 하고 첫 번째 숫자는 부등호와 상관없이 s 문자열에 포함되어야 하는 부분을 신경 써주면 된다.

가장 중요한 부분은 부등호에 맞게 큰 값과 작은 값이 들어가야 하는 분기를 다르게 설정해주어야 한다.
본인은 '<' 부등호 일 때, s[-1] 문자열의 가장 뒷 부분의 문자와 해당 숫자를 비교해서 부등호에 맞는 숫자를 s 문자열에 추가시키는 방향으로 구현하였다.

 

 

2. 정답코드

import sys
input = sys.stdin.readline


k = int(input())
strings = list(map(str, input().split()))


# dfs
def dfs(idx, s, s_number):
    global result, max_v, min_v

    # 종료 지점
    if idx > k:
        max_v = max(str(max_v), s)
        min_v = min(str(min_v), s)
        return

    for i in range(10):
        if chk[i] == False:
            if idx == 0:
                chk[i] = True
                dfs(idx + 1, s + str(i), s_number)
                chk[i] = False
            elif idx > 0:
                if strings[s_number] == '<' and s[-1] < str(i):
                    chk[i] = True
                    dfs(idx + 1, s + str(i), s_number + 1)
                    chk[i] = False
                elif strings[s_number] == '>' and s[-1] > str(i):
                    chk[i] = True
                    dfs(idx + 1, s + str(i), s_number + 1)
                    chk[i] = False


# main
chk = [False] * (10)
max_v, min_v = -1e9, sys.maxsize

dfs(0, "", 0)
print(max_v)
print(min_v)