알고리즘 - Python / 백준 - 2293번 : 동전 1

2293번: 동전 1 (acmicpc.net)

2293번: 동전 1

 

---

풀이

• 대표적인 DP 문제인 동전 문제다.
• 동전이 주어지고 , 그 동전들을 가지고 해당 금액을 만들 수 있는 경우의 수를 구하는 문제다.
• DP 점화식은 DP[I] = DP[I-K] + DP[I] 로 I 금액을 K 금액의 동전으로 만드는 경우를 이야기한다.
• 만약 1원 2원을 가지고 17원을 만드는 경우는 16원을 만드는 경우에 1원 동전을 사용하는 경우 , 15원을 만드는 경우에 2원 동전을 사용하는 경우 2가지 일 것이다.
• 위와 같은 방식으로 DP 배열을 채우고 DP[만들고 싶은 금액] 의 값을 출력하면 된다.
• 2293 동전 1 과 비슷한 문제로는 9084 동전 문제가 있다.

 

 

 

알고리즘 - Python / 백준 - 9084번 : 동전 (tistory.com)

알고리즘 - Python / 백준 - 9084번 : 동전

 

 

 

import sys
n , money= map(int ,sys.stdin.readline().split(" "))
c = []
for i in range(n):
    c.append(int(sys.stdin.readline()))

dp = [0 for i in range(money+1)]
dp[0] = 1
for i in c:
    for o in range(1,money+1):
        if o >= i:
            dp[o] = dp[o] + dp[o-i]
print(dp[money])

---