백준 2204 파이썬 문제 풀이

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

접근 방법

1. 완전탐색

: 먼저 완전탐색으로 접근할 수 있는지를 살펴본다. 숫자가 100개가 주어진다. 100개가 k값을 만족하기 위해서 완전탐색을 하는데 얼마만큼의 경우의 수가 발생할까? 나는 아직 시간복잡도에 익숙하지는 않아, 정확하게 말을 하기는 어렵지만.. 대략적으로 살펴보면 적어도 n^2 이상의 시간 복잡도가 필요할 것으로 예상된다. 따라서, 자세하게 구현을 하려고 하진 않았지만 안될 것 같아 접근하지 않았다.

2. 다이나믹 프로그래밍

: 다이나믹 프로그래밍으로 바텀업 방식으로 접근을 하기로 했다. 왜냐하면 작은 문제를 풀면서 큰 문제를 풀 수 있는 것으로 해석이 되었기 때문이다. 예시를 바탕으로 다시 한번 정리해보면 다음과 같다.

1을 만드는 최소의 경우의 수를 먼저 확인한다. 1로만 만들 수 있다. 2를 만드는 최소의 경우의 수는 1이 2개, 4까지는 각각 1이 n개만큼 필요하다.

그런데 5를 만들 때, 새로운 분기점이 발생한다. 5를 만들 때는 5를 1개로만 구성하는 것이 가장 저렴하다. 그 다음은 6을 만들 때를 들여다 볼 수 있다. 6을 만들 때는 1을 만드는 최소 동전수에서 5를 1개 더하는 방법과 5를 만드는 최소 동전수에서 1개 더하는 방법 중, 가장 적은 값이 들어간다. 

즉, 다음과 같은 점화식이 만들어진다. (c1,c2,c3,c4...cp)는 주어진 동전 갯수다, 여기선 1,2,5)

d[i] = min( d[i-c1] + 1 , d[i-c2] + 1, ....  d[i-cp[)

최소값을 항상 기록해야하는 것이기 때문에 d는 가장 큰 수로 초기화를 시켜주었다. 코드는 아래와  같다.

import sys
n,k = map(int,sys.stdin.readline().split())
coin = set()
for i in range(n) :
    coin.add(int(sys.stdin.readline().rstrip()))
d = [10000000000 for _ in range(k+1)]
cnt = 1
for i in coin :
    cnt = 1
    while 1 :
        if i*cnt > k :
            break
        d[i*cnt] = cnt
        cnt+=1

for i in range(1,k+1) :
    for j in coin :
        if i-j > 0 :
            temp = d[i-j] + 1
            if d[i] > temp :
                d[i] = temp


if d[k] == 10000000000 :
    print(-1)
else :
    print(d[k])