[백준(Baekjoon)] 2294 동전 2

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

3 15
1
5
12

예제 출력 

3

 

---

나의 코드

[Python(파이썬)]

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
case = [0]+[10001]*k

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

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

 

---

풀이

 

<동전 0 문제>

[백준(Baekjoon] 11047 동전 0

 

• 동전 0, 동전 2 문제 공통점

n가지 종류의 동전을 적당히 사용해서, 그 가치의 합이 k원이 되는 최소 동전 개수를 구하는 문제이다. 

 

• 동전 0, 동전 2 문제 차이점

동전 0 문제는 동전이 모두 배수로 이루어져있어 그리디를 사용한 문제라면

동전 2 문제는 동전들이 배수로 이루어져 있지 않아 동적 계획법을 이용하는 문제이다. 

 

 

<동적 계획법>

[Algorithm] Dynamic Programming(동적 계획법, 다이나믹 프로그래밍)

 

 

• case 리스트 

case의 인덱스 값 = 가치의 합(k원)

case[인덱스] = 인덱스(k원)를 만드는데 필요한 최소의 동전 개수

 

case = [0]+[10001]*k

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

 

ex)

3 8

1

4

7

 

처음 상황

case = [0, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001]

coins = [1, 4, 7]

 

진행 과정

1. coin = 1 : 1원으로 구성할 수 있는 최소의 개수 구하기

case[4] = 4 -> 4원을 만드려면 1원 4개

case[5] = 5 -> 5원을 만드려면 1원 5개

case = [0, 1, 2, 3, 4, 5, 6, 7, 8]  -> 1원으로만 구성

 

2. coin = 4 

case[4] = 1 -> 4원을 만드려면 4원 1개  -> min(case[i](1원 4개), case[i-coin]+1(4원 1개)) -> min(4, 1) -> 1

case[5] = 2 -> 5원을 만드려면 4원 1개, 1원 1개  -> min(case[i](1원 5개), case[i-coin]+1(4원 1개, 1원 1개)) -> min(5, 2) -> 2

case[i-coin]+1 => case[5-4] : case[1] (1원을 만들 수 있는 최소의 개수:1) + 1 (4원 1개) 

case[7] = 4 -> 7원을 만드려면 4원 1개, 1원 3개  -> min(case[i](1원 7개), case[i-coin]+1(4원 1개, 1원 3개)) -> min(7, 4) -> 4

case[i-coin]+1 => case[7-4] : case[3] (3원을 만들 수 있는 최소의 개수:3) + 1 (4원 1개) 

case[8] = 2 -> 8원을 만드려면 4원 2개 -> min(case[i](1원 8개), case[i-coin]+1(4원 2개)) -> min(8, 2) -> 2

case[i-coin]+1 => case[8-4] : case[4] (4원을 만들 수 있는 최소의 개수:1) + 1 (4원 1개) 

case = [0, 1, 2, 3, 1, 2, 3, 4, 2] -> 1원, 4원으로 구성할 수 있는 최소의 개수

 

3. coin = 7

case[4] = 1 -> 4원을 만드려면 4원 1개

case[5] = 2 -> 5원을 만드려면 4원 1개, 1원 1개

case[7] = 1 -> 7원을 만드려면 7원 1개 -> min(case[i](4원 1개, 1원 3개), case[i-coin]+1(7원 1개)) -> min(4, 1) -> 1

case[i-coin]+1 => case[7-7] : case[0] (0원을 만들 수 있는 최소의 개수:0) + 1 (7원 1개) 

case[8] = -> 8원을 만드려면 4원 2개 or 1원 1개, 7원 1개-> min(case[i](4원 2개), case[i-coin]+1(1원 1개, 7원 1개)) -> min(4, 1) -> 1

case[i-coin]+1 => case[8-7] : case[1] (1원을 만들 수 있는 최소의 개수:1) + 1 (7원 1개) 

case = [0, 1, 2, 3, 1, 2, 3, 1, 2]  -> 1원, 4원, 7원으로 구성할 수 있는 최소의 개수

 

 

---

문제 출처

2294번: 동전 2