백준 boj 2529 - 부등호 (파이썬, python)

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

2529번: 부등호

 

백트래킹을 이용하여 풀었다.

부등호들은 brackets라는 배열로 관리하였고,

dfs로 체크하는 동안 check_up이라는 함수를 통해 부등호가 만족하는지 확인하였고, 

만족하는 것들은 배열에 담아두었다가 dfs가 끝나면 맨 처음 것과, 마지막 것을 출력해주었다.

 

code

 

n = int(input())
brackets = list(input().split())
visited = [0] * 10
ans = []

def check_up(i, j, k):
    if k == '<':
        return i < j
    else:
        return i > j

def dfs(iter, temp):
    if iter == n + 1:
        ans.append(temp)
        return

    for i in range(10):
        if not visited[i]:
            if iter == 0 or check_up(temp[-1], str(i), brackets[iter - 1]):
                visited[i] = 1
                dfs(iter + 1, temp + str(i))
                visited[i] = 0
dfs(0, "")

print(ans[-1])
print(ans[0])