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

선주·2022년 3월 19일

알고리즘

Python PS

목록 보기

61/65

📌 문제

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

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

입력

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

출력

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

예제 입력 1

예제 출력 1

📌 풀이

💬 Code

import sys
input = sys.stdin.readline

n, k = map(int, input().split())  # 동전종류 n가지로 k원 만들기
coins = set()
for _ in range(n):
    coins.add(int(input()))

dp = [0] * (k+1)  # dp[i]는 i원을 만들기 위해 필요한 동전의 최소 개수
for i in range(1, k+1):
    tmp = []
    for coin in coins:
        if i >= coin and dp[i-coin] != -1:
            tmp.append(dp[i-coin]+1)
    if not tmp:
        dp[i] = -1
    else:
        dp[i] = min(tmp)

print(dp[k])

💡 Solution

DP는 너무 어려워,,,,, 도저히 모르겠어서 구글링함 ㅋ
가치가 같은 동전이 여러 번 주어질 수도 있다는 조건이 주어져서 중복 처리를 위해 coins를 set으로 만들어줬고, coins에 동전 종류들을 담았다.

dp[i]는 i원을 만들기 위해 필요한 동전의 최소 개수를 나타낸다.
주어진 예제의 경우 dp[i]는 다음과 같다.

dp[0] = 0개
dp[1] = 1개 (1)
dp[2] = 2개 (1, 1)
dp[3] = 3개 (1, 1, 1)
dp[4] = 4개 (1, 1, 1, 1)
dp[5] = 1개 (5)
dp[6] = 2개 (5, 1)
dp[7] = 3개 (5, 1, 1)
dp[8] = 4개 (5, 1, 1, 1)
dp[9] = 5개 (5, 1, 1, 1, 1)
dp[10] = 2개 (5, 5)
dp[11] = 3개 (5, 5, 1)
dp[12] = 1개 (12)
dp[13] = 2개 (12, 1)
dp[14] = 3개 (12, 1, 1)
dp[15] = 3개 (5, 5, 5)

위의 경우로 미루어 보았을 때, 점화식은 dp[i] = min(dp[i-coin]+1)이다. coin은 coins에 담긴 모든 원소를 반복문으로 탐색한다.

예를 들어 dp[15]는 dp[15-1]+1, dp[15-5]+1, dp[15-12]+1 중 가장 작은 값이 된다.

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