[백준 1040번] 정수 (Python3)

from itertools import *

def solve():
  if len({*N})==K:
    return N
  for i in range(1,len(N)+1):
    result = []
    inuse = {*(N0:=N[:-i])}; notuse = {*map(str,range(10))}-inuse; k = K-len(inuse)
    if 0<=k<=i:
      for C in combinations(notuse,k):
        C = {*C}
        for H in combinations_with_replacement(inuse|C,i-k):
          willuse = [*H,*C]
          for n in range(int(N[-i])+1,10):
            n = str(n)
            if n in willuse:
              willuse.remove(n)
              result.append(N0+n+"".join(sorted(willuse)))
      if result:
        return min(result)
  return "1"+"0"*(max(len(N)+1,K)-K+1)+"".join(map(str,range(2,K)))

N,K = input().split(); K = int(K)
print(solve())

조합과 중복조합으로 해결하였다.

디지털 카운터 [백준 1020번] 디지털 카운터 (Python3) (tistory.com) 문제와 유사한 방식으로 해결하였다.

 

풀이를 설명하면,

1. 숫자를 1~L(L=len(N))=i 자리수까지 자른다.

2. 잘라내고 남은 숫자들을 구성하는 숫자들을 inuse로 저장하고, notuse에 0~9 중에서 inuse에 포함하지 않은 숫자들을 저장한다.

3. notuse에서 K-(inuse 개수)=k개의 숫자를 combinations으로 뽑고 com으로 저장한다.

4. i-k개의 숫자를 inuse와 com을 합친 집합에서 중복조합으로 뽑는다.

5. 3에서 뽑은 숫자와 4에서 뽑은 숫자를 중 원래 숫자보다 크면서 가장 작게끔 정렬하고 result에 넣는다.

6. result에서 가장 작은 값을 출력하고, result에 숫자가 없으면 자릿수를 늘려가며 반복한다.

7. 자리수를 L까지 했는데도 찾지 못했다면 "1"+"0*(max(L+1,K)-K+1)"+"2~K까지 숫자"를 출력한다. (예를들어 L=3, K=5라면 10234 출력)

 

중복조합을 이용해서 간단하게 해결하였다. 이 문제도 디지털 카운터 문제처럼 조합을 이용하는것이 아닌 DP를 이용해서 푸는 문제라고 한다. DP를 이용한 풀이도 한번 고민해보아야겠다.

 

 

오늘의 교훈) itertools는 유용하다.