[Python]2294번, 동전 2

목차

 

문제

 

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 

 

그러면서 동전의 개수가 최소가 되도록 하려고 한다. 

 

각각의 동전은 몇 개라도 사용할 수 있다.

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

 

입력

 

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 

 

다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 

 

동전의 가치는 100,000보다 작거나 같은 자연수이다. 

 

가치가 같은 동전이 여러 번 주어질 수도 있다.

 

출력

 

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

 

풀이

 

동전의 종류가 특별하지 않고 일반적인 경우 특정 금액을 만드는 동전의 최소 개수를 구하는 문제이다.

 

문제를 푸는 알고리즘은 다음과 같다.

 

1. dp 리스트 초기화
   먼저 dp[0]을 제외한 모든 값을 10001로 초기화한 길이 (k + 1)의 리스트 dp를 생성한다.
   이는 k의 값이 최대 10000이기 때문이며, dp[0]의 경우만 0으로 초기화한다.
   이 리스트는 당연하게도 금액 별로 필요한 최소 동전 개수를 저장하는 데 사용한다.
2. 이중 반복문을 돌며 탐색
   이제 반복문을 돌며 각 금액별로 필요한 최소 동전 개수를 계산한다. 구체적으로는 다음과 같은 과정을 거친다.
   
   
   1. 먼저 현재 금액에서 각 동전의 가치를 뺀 금액은 이미 최소 동전 개수가 계산되어 있다 가정한다.
   2. 그러므로 이전 단계에서 계산한 dp[현재 금액 - 동전 가치] 값을 사용한다.
   3. 현재 금액에서 각 동전의 가치를 뺀 금액에 1을 더하면 현재 금액을 만들기 위한 동전의 최소 개수가 된다.
   4. 따라서 dp[현재 금액]은 위의 두 값 중 작은 값이 된다.
3. 출력

예시로 동전의 가치가[1, 2, 5]이고 목표 금액이 11인 경우에 대해 살펴보자.

 

1. dp 리스트는 [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]로 초기화한다.
2. 먼저 1원 동전을 고려해 dp 리스트를 업데이트한다.
   
   
   1. dp[1]은 dp[1 - 1] + 1과 dp[1]중 작은 값으로 갱신된다. 결과는 1이다.
   2. dp[2]는 dp[2 - 1] + 1과 dp[2]중 작은 값으로 갱신된다. 결과는 2이다.
   3. dp[3]은 dp[3 - 1] + 1과 dp[3]중 작은 값으로 갱신된다. 결과는 3이다.
   4. dp[4]는 dp[4 - 1] + 1과 dp[4]중 작은 값으로 갱신된다. 결과는 4이다.
   5. 이런 식으로 갱신하면 dp[11]은 11이 된다.
3. 이어서 2원 동전을 고려해 dp 리스트를 업데이트한다.
   
   
   1. dp[2]는 dp[2 - 2] + 1과 dp[2]중 작은 값으로 갱신된다. 결과는 1이다.
   2. dp[3]은 dp[3 - 2] + 1과 dp[3]중 작은 값으로 갱신된다. 결과는 2이다.
   3. dp[4]는 dp[4 - 2] + 1과 dp[4]중 작은 값으로 갱신된다. 결과는 2이다.
   4. dp[5]는 dp[5 - 2] + 1과 dp[5]중 작은 값으로 갱신된다. 결과는 3이다.
   5. 이런 식으로 갱신하면 dp[11]은 6이 된다.
4. 마지막으로 5원 동전을 고려해 dp 리스트를 업데이트한다.
   
   
   1. dp[5]는 dp[5 - 5] + 1과 dp[5]중 작은 값으로 갱신된다. 결과는 2이다.
   2. dp[6]은 dp[6 - 5] + 1과 dp[6]중 작은 값으로 갱신된다. 결과는 2이다.
   3. dp[7]은 dp[7 - 5] + 1과 dp[7]중 작은 값으로 갱신된다. 결과는 2이다.
   4. dp[8]은 dp[8 - 5] + 1과 dp[8]중 작은 값으로 갱신된다. 결과는 3이다.
   5. dp[9]는 dp[9 - 5] + 1과 dp[9]중 작은 값으로 갱신된다. 결과는 3이다.
   6. dp[10]은 dp[10 - 5] + 1과 dp[10]중 작은 값으로 갱신된다. 결과는 3이다.
   7. dp[11]은 dp[11 - 5] + 1과 dp[11]중 작은 값으로 갱신된다. 결과는 3이다.
5. 최소 동전의 개수는 3이다.

 

Python

 

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())
coins = []

for _ in range(n):
    coins.append(int(sys.stdin.readline()))

dp = [10001] * (k + 1)
dp[0] = 0

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

if dp[k] == 10001:
    print(-1)
else:
    print(dp[k])