[백준알고리즘] 2294번: 동전 2 -Python

[백준알고리즘] 2294번: 동전 2 -Python

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

2294번: 동전 2

동적 계획법을 사용해서 문제를 풀었다.

 

주어진 코인으로 1부터 k까지 차례대로 만들 때 사용하는 코인의 최소 개수를 저장하도록 했다.

 

각 금액을 만들 때 모든 코인들을 사용해본다. 현재 만들려는 금액이 t라면, 각 코인을 사용해서 t가 되었다고 생각을 하면 된다.

 

주어진 예제입력을 예시로 들어보겠다.

1부터 만들도록 하자. 

 

코인(1)을 사용해서 1을 만들도록 했을 때, 0일 때 코인(1)을 사용하는 방법밖에 없다.

코인(5)과 코인(12)으로는 1이라는 값을 만들 수 없다.

 

마찬가지로 6을 만들려고 해보자.

값이 5일 때 코인(1)을 사용하는 방법과 값이 1일 때 코인(5)을 사용하는 방법이 있다.

5일 때의 코인 사용의 최소 개수는 1이며 1일때 코인 사용의 최소갯수도 1이기 때문에, min(1+1, 1+1)로 6을 만들때 사용하는 코인의 최소갯수는 2개이다.

 

14를 만들려고 생각해보자.

값이 13일 때 코인(1)을 사용하는 방법과 값이 9일때 코인(5)를 사용하는 방법과 값이 2일때 코인(12)를 사용하는 방법이 있다.

값이 13일때 사용한 코인의 최소 개수는 2

값이 9일 때 사용한 코인의 최소 개수는 5

값이 2일 때 사용한 코인의 최소개수는 2

따라서 값을 14로 만들기 위해 사용하는 코인의 최소 갯수는 3개이다.

 

n, k = map(int, input().split())
coin = sorted(list(set(int(input()) for _ in range(n))))
dp = [20000] * 10001
dp[0] = 0

for i in range(1, k+1):
    for c in coin:
        if i-c < 0:
            break
        dp[i] = min(dp[i], dp[i-c]+1)
        
print(dp[k] if dp[k] != 20000 else -1)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다