[백준 1020번] 디지털 카운터 (Python3)

from itertools import combinations_with_replacement as comb

def solve():
  for c in range(1,C+1):
    N0 = N[-c:]
    S = sum(cnt[int(n)] for n in N0)
    result = []
    for pick in comb(num,c):
      if sum(pick)==S:
        for n in range(int(N0[0])+1,10):
          if cnt[n] in pick:
            pick = [*pick]
            pick.remove(cnt[n])
            result.append(int(str(n)+"".join(map(str,sorted(num[n] for n in pick)))))
            break
    if result:
      return min(result)-int(N0)
  result = []
  for pick in comb(num,C):
    if sum(pick)==S:
      result.append(int("".join(map(str,sorted(num[n] for n in pick)))))
  return 10**C+min(result)-int(N)

cnt = [6,2,5,5,4,5,6,3,7,5]; num = {2:1,3:7,4:4,5:2,6:0,7:8}
C = len(N:=input())
print(solve())

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

 

풀이를 설명하면,

1. 각 숫자의 선분의 개수를 cnt로 저장하고, 선분의 개수들에 해당하는 숫자 중 가장 작은 숫자를 num에 저장한다.

2. 입력받은 숫자의 자리수를 C라고 할때, 1~C까지 숫자 N을 해당자릿수까지만 남기고 잘라낸 것을 N0라고 한다. (예를들어 N = 12345일때 c = 2이면 N0 = 45이다)

3. N0의 선분의 개수의 총합을 S로 두고, 각 숫자의 선분의 개수에 해당하는 2,3,4,5,6,7 중에서 c개를 중복조합으로 뽑아 합이 S가 되는 경우를 찾는다.

4. 합이 S가 되는 경우 N0의 첫번째 자리수 숫자를 n이라 할때, n+1~9 중 중복조합에 포함되는 개수에 해당하는 숫자 중 가장 작은 숫자를 첫번째 자리수로 놓고, 나머지는 크기가 가장 작아지도록 정렬한 숫자를 result에 넣는다.

5. result에 숫자 중 가장 작은 값과 N0와의 차이를 출력하고, result에 숫자가 없으면 자릿수를 늘려가며 반복한다.

6. 자리수를 C까지 했는데도 찾지 못했다면 첫번째 자리수를 정하지 않고 합이 S가 되는 가장 작은 수를 구한 뒤, N과의 차이+10**C를 출력한다.

 

itertools에 중복조합이 있다는 사실을 알게 된 문제였다. 다른 사람들 풀이를 보니 DP로 해결한 사람들이 많아보였다. DP로 해결하는 방법도 한번 고민해봐야겠다.

 

 

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