[백준`G5] 2294 - 동전 2 (Python)

문제 설명

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

2294번: 동전 2

 

성능 요약

메모리: 31120 KB, 시간: 288 ms

 

분류

다이나믹 프로그래밍

 

제출 일자

2024년 3월 22일 02:24:34

 

문제 설명

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

 

입력

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

 

출력

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

 

---

문제 설명

DP의 가장 기본인 문제

이 문제를 안 풀었으면 DP를 안다고 할 수 없음(?)

알고리즘 수업 들었을 당시에 과제로 했었는데 너무 오래 전이라 다시 풀어봤다

DP 문제를 몇 번 풀어보니 점화식 생각하는 게 조금 수월해진 느낌...?

 

점화식은 min(dp[i - coin] + 1) 이다.

동전들을 탐색하며 동전 조합들을 저장하고, 그 중 가장 개수가 작은 것을 dp에 저장했다.

조건에 ' 가치가 같은 동전이 여러 번 주어질 수도 있다.' 라는 말이 있길래 동전들의 종류는 set으로 선언한 후 add했다.

n, k = list(map(int, input().split()))
coin = set()
for _ in range(n):
    coin.add(int(input()))
dp = [0] * (k+1)

for i in range(1, k+1):
    temp = []
    for c in coin:
        if i >= c and dp[i-c] != -1:
            temp.append(dp[i-c] + 1)
    if not temp:
        dp[i] = -1
    else:
        dp[i] = min(temp)

print(dp)