https://www.acmicpc.net/problem/2529
접근
- 0 ~ 9까지 순회하면서 dfs 탐색한다.
- 해당 숫자가 부등호를 만족하면 방문 처리한다.
- 만족하는 숫자를 모두 뽑으면(K + 1개) 최댓값과 최솟값을 갱신하고 탐색을 종료한다.
풀이
from sys import stdin
def dfs(r, num):
global min_result, max_result
if r == K + 1:
if int(min_result) > int(num):
min_result = num
if int(max_result) < int(num):
max_result = num
return
for i in range(10):
if visited[i]:
continue
if r == 0 or check_sign(signs[r - 1], int(num[-1]), i):
visited[i] = True
dfs(r + 1, num + str(i))
visited[i] = False
def check_sign(sign, num1, num2):
if sign == ">":
return num1 > num2
else:
return num1 < num2
K = int(stdin.readline())
signs = stdin.readline().split()
visited = [False] * 10
min_result = "9876543210"
max_result = "0"
dfs(0, "")
print(max_result)
print(min_result)