파이썬 백준 11047 동전

import sys
input = sys.stdin.readline
from math import gcd
 
n, k = map(int, input().split())
C = []
lcm = 1
maxc = 0
for i in range(n) : 
    c = int(input())
    C.append(c)
    lcm = lcm * c // gcd(lcm, c)
    maxc = max(maxc, c)
 
cycle = lcm // maxc
cycnt = (k // lcm) * cycle
k = k % lcm
count = [0 for i in range(k + 1)]
for now in range(1, k + 1) : 
    before = []
    for coin in C : 
        if coin <= now and count[now - coin] != -1:
            before.append(count[now - coin])
    if not before : 
        count[now] = -1
    else:
        count[now] = min(before) + 1
print(cycnt + count[k])

IDEA

DP를 이용한 동전 문제와 똑같지만, k가 매우 크다.

크기 k의 DP table을 만들지 않고, 적절한 아이디어를 통해 k의 규칙성을 찾아 전처리를 해야할 것이다.

 

k가 주어진 모든 동전 값의 공배수일 때, 필요한 최소 갯수는 가장 큰 동전 하나만 쓰는 것이다.

예를 들어 10, 50, 100, 500원 동전이 있을 때, k가 최소공배수 500의 배수라면 500원 동전만 쓰면 된다.

30, 40원 동전이 있을 때 k가 120의 배수라면 40원 동전만 쓰면 된다.

이를 이용하여 동전간의 최소공배수를 구하고, k를 그것으로 나눈 나머지에 대해서만 DP를 돌린다.

 

line 9 ~ 13

동전의 가격을 인풋받을 때, 가장 큰 동전 maxc와 동전들의 최소공약수 lcm도 구한다.

두 수의 최소공배수는 두 수의 곱을 최대공약수로 나눈 값이다.

gcd를 import하여 새 동전 c를 받을 때마다 lcm * c / gcd를 반복함으로써 모든 동전간의 lcm을 구할 수 있다.

 

line 15 ~ 17

lcm을 가장 큰 동전으로 나눈 값이 lcm을 동전들로 채우는 최소 갯수이다. 이를 cycle이라 하자.

k를 lcm으로 나눈 몫(k//cycle)에 cycle을 곱하면 k의 lcm 배수 부분을 동전들로 채우는 갯수(cycnt)는 구해진다.

이제 나머지 k%cycle을 다시 k로 두고 이 충분히 작은 k에 대해 DP로 횟수를 구하면 된다.