[백준/Python] 2294_동전2

문제

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

2294번: 동전 2

코드

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())
coins = []  # 동전의 가치
for _ in range(n):
    coins.append(int(sys.stdin.readline().rstrip()))
dp = [-1] * (k + 1)  # 초기화
dp[0] = 0  # 초기값
for i in range(1, k + 1):
    for j in range(n):
        if coins[j] <= i and dp[i - coins[j]] != -1:
            if dp[i] == -1:  # dp에 처음 입력할 때
                dp[i] = dp[i - coins[j]] + 1
            elif dp[i] != -1:
                dp[i] = min(dp[i], dp[i - coins[j]] + 1)  # (dp[i - coins[j]] + 1)의 최소값을 dp[i]에 저장
print(dp[-1])

풀이

DP를 이용합니다.

문제의 예제를 dp 테이블로 나타내면 아래와 같습니다.

idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
dp	0	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

입력받은 동전들을 coins 리스트에 넣습니다.

(k + 1) 길이의 dp를 선언하고 전부 -1값을 넣어서 초기화합니다.

dp[0] = 0 으로 초기값을 넣습니다.

2중 반복문으로 idx 1부터 순회하고 coins 리스트값들을 전부 확인하면서 (dp[idx - coin의 가치] + 1)값 중에서 최소값을 dp[idx]에 저장합니다.

최종적으로 dp 리스트의 마지막 항이 답이 됩니다.