백준 2529번 부등호 (Python 3)

Baekjoon online judge 2529번 파이썬

 

링크

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

2529번: 부등호

permutations 이용해서 풀어도 10! = 3628800 개 만 확인하면 되기 때문에 풀린다.

백트래킹을 이용해서 풀었다.

지금까지의 숫자 문자열을 들고다니면서, 문자열의 길이가 k+1이 되었을 때 max,min 값을 갱신한다.

 

소스코드

import sys
input = sys.stdin.readline
now_min=sys.maxsize
now_max=-1
k=int(input())
op=list(map(str,input().split()))
chk=[False for _ in range(10)]

def f(s):
  global now_max
  global now_min
  if len(s)==k+1:
    now_max=max(now_max,int(s))
    now_min=min(now_min,int(s))
    return

  for i in range(10):
    if chk[i]:
      continue

    if len(s)==0 or eval(s[-1]+op[len(s)-1]+str(i)):
      chk[i]=True
      f(s+str(i))
      chk[i]=False

f('')
print(str(now_max).zfill(k+1))
print(str(now_min).zfill(k+1))