[백준/2294] 동전 2 (Python)

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

2294번: 동전 2

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:03:23

 

 

---

 

문제 설명

 

 

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

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

3 15
1
5
12

 

출력 예시

 

3

 

 

---

 

풀이

 

바로 어제 풀이했던 동전 문제와 거의 유사하다. 핵심적인 접근은 2차원 DP(최대 시간복잡도 O(nk))를 이용하는 것이며, 문제 풀이 시 몇 가지만 조금 바꾸어 생각해보면 된다.

 

2023.06.07 - [알고리즘 문제/백준] - [백준/9084] 동전 (Python)

[백준/9084] 동전 (Python)

 

• 동전 조합의 경우의 수가 아닌, 조합 시 최소 동전 개수를 풀이하는 것이므로, 합이 아닌 minimal value를 반환한다. 즉 식이 dp[coin + i] += dp[i] 에서 dp[coin + i] = min(dp[coin + i], dp[i] + 1) 로 변환된다.
  • 마지막에 minimal value가 업데이트되지 않은 경우는 모든 조합에서 k원을 반환하는 게 불가능하다는 의미가 되므로, -1를 반환한다.
• 동전의 가치가 중복될 수 있으나, 동전 자체가 중복되지는 않는다. 따라서 위 DP 풀이에 변화를 주지 않는다. 

 

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = float('inf')

n, k = map(int, input().split())
coin_list = [int(input()) for _ in range(n)]
dp = [MAX]*(k+1)
dp[0] = 0

for coin in coin_list :
  for i in range(k-coin+1) :
    dp[i+coin] = min(dp[i+coin], dp[i] + 1)

print(dp[-1] if dp[-1] < MAX else -1)

풀이 완료!