[BOJ] 백준 2293 동전 1 Python

2293번: 동전 1

문제풀이
경우의 수 문제이며 메모리 제한과 시간 제한을 따져봤을 때 DP를 사용해서 풀어야함을 알 수 있었다.
k원을 만들기 위해 1 <= i <= k 의 범위 내에서 1원...2원...3원...~...k원이 되는 경우의수를 구해야한다.
또한, dp배열의 인덱스는 i로 i원이 되는 경우의 수는 dp[i]가 된다는 것은 명확하다.
방금 파악한 내용을 바탕으로 입력값 예제에 대한 문제를 해결해보자.

입력예제
3 10
1
2
5

1.
1원으로 k원을 만들 수 있는 경우의 수
1원으로 1원을 만들 수 있는 경우의 수 : 1 → (1)
1원으로 2원을 만들 수 있는 경우의 수 : 1 → (1,1)
.
.
.
1원으로 k원을 만들 수 있는 경우의 수 : 1 → (1,1,1,...,1) <k개의 1>

2.
2원으로 k원을 만들 수 있는 경우의 수
2원으로 2원을 만들 수 있는 경우의 수 : 2 → (1,1),(2)
2원으로 3원을 만들 수 있는 경우의 수 : 2 → (1,1,1),(1,2)
2원으로 4원을 만들 수 있는 경우의 수 : 3 → (1,1,1,1),(1,1,2),(2,2)
2원으로 5원을 만들 수 있는 경우의 수 : 3 → (1,1,1,1,1),(1,1,1,2),(1,2,2)

여기까지 했을 때 이 항들에 대한 점화식을 찾을 수 있었다.
점화식 : dp[i] = dp[i] + dp[i - 동전value] (가능범위 : 동전value <= i <=k )

이 점화식을 토대로 코드를 만들었다.

---

Code

from sys import stdin

input = stdin.readline


def solve():
    coin = []
    n, k = map(int, input().split())
    for _ in range(n):
        coin.append(int(input()))
    dp = [0] * (k + 1)
    dp[0] = 1
    for c in coin:
        for i in range(c, k + 1):
            dp[i] += dp[i - c]
    print(dp[-1])


solve()