[Python] 백준 2293 - 동전 1 문제 풀이

Overview

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

---

문제 페이지

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

---

풀이 코드

from sys import stdin


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

    dp = [1] + [0] * k

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

    print(dp[k])


if __name__ == "__main__":
    main()
    

다이나믹 프로그래밍을 이용하여 순서가 없는 동전 선택 경우의 수를 구한다.

주의해야할 점은 위 코드에서

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

이 부분을

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

이렇게 풀이한다면, 순서가 있는 동전 선택 경우의 수가 구해진다. 즉, 같은 동전 조합들이 중복해서 구해진다.