백준 2529 부등호

문제

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

풀이

백트래킹으로 모든 경로를 하나씩 찾아보면서, 잘못 가지치기를 한 경우 백트래킹을 해주면 된다. 백트래킹은 말 그대로 한번 갔다가 다시 이전 상태를 만들어야 하기 때문에, ‘방문처리 -> 재귀 -> 방문처리 풀기’ 의 과정이 동반된다.
가지치기로 쭉 내려가 cnt 개수 비교를 통해, 부등호의 식을 모두 다 채웠다면 문제에서 요구한 사항을 채워주면 된다. 사전순으로 나열했을때 제일 처음부터 마지막까지 브루트 포스를 하기 때문에 제일 처음 나온것과 제일 마지막에 나온것을 저장해주면 된다.

n = int(input())
op = list(input().split())
visited = [0]*10
arr = [-1]*10
first = ''
end = ''
def go(idx,cnt):
  global first,end
  if cnt == n+1:
    res = ''
    for i in range(n+1):
      res += str(arr[i])
    if first == '': first = res
    end = res
    return
  for i in range(10):
    if not visited[i]:
      if idx > 0:
        if op[idx-1] == '<' and arr[idx-1] < i:
          arr[idx] = i
          visited[i] = 1
          go(idx+1,cnt+1)
          arr[idx] = -1
          visited[i] = 0
        elif op[idx-1] == '>' and arr[idx-1] > i:
          arr[idx] = i
          visited[i] = 1
          go(idx+1, cnt+1)
          arr[idx] = -1
          visited[i] = 0
      else:
        arr[idx] = i
        visited[i] = 1
        go(idx+1,cnt+1)
        arr[idx] = -1
        visited[i] = 0
go(0,0)
print(end)
print(first)

boj 카테고리 내 다른 글 보러가기