[Python] 백준 2294 - 동전 2 문제 풀이

Overview

BOJ 2294번 동전 2 Python 문제 풀이
분류: Dynamic Programming (동적계획법)

---

문제 페이지

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

---

풀이 코드

from sys import stdin


INF = 10001


def main():
    n, k = map(int, stdin.readline().split())
    coins = set(int(stdin.readline()) for _ in range(n))

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

    print(dp[k]) if dp[k] != INF else print(-1)


if __name__ == "__main__":
    main()

다이나믹 프로그래밍을 이용하여 dq 리스트에 최소 동전 개수를 저장한다.