[Python] 백준 #2293- 동전 1

문제

---

2293번: 동전 1

코드

---

My answer

import sys
from itertools import combinations
input=sys.stdin.readline

n,k=map(int,input().split())
coin=[]
dp=[1]+[0 for i in range(k)]

for i in range(n):
    coin.append(int(input()))

for i in range(len(coin)):
    for j in range(0,k+1):
        if(j-coin[i]>=0):
            dp[j]+=dp[j-coin[i]]
print(dp[k])

Another answer

n,k=map(int,input().split())
l=[1]+[0]*10000
for i in'a'*n:
 x=int(input())
 for j in range(k-x+1):
 	l[j+x]+=l[j]
print(l[k])

 

풀이

---

dp문제라서 역시나 규칙 찾기가 너무 힘들었다. 이 문제의 규칙은 쉽게 생각하면 dp[1]=1원을 만들 수 있는 경우의 수를 의미하고 dp[n]은 dp[n-가지고있는 종류의 동전] 예를 들어 1,2,5원이면 dp[n]=dp[n]+dp[n-1]+dp[n-2]+dp[n-5]이다. n이 10이고 가지고 있는 동전이 1,2,5이면 dp[10]=dp[9]+dp[8]+dp[5]이다. dp[9]로 9원을 어떻게든 만들고 1원을 더하고, dp[8] 8원을 만드는 방법에 2동전한개를 더하고 dp[5] 5원을 만드는 방법에 5원 짜리 동전을 하나 더하는 것이다. 이걸 역순으로 하면 문제가 풀린다. ..설명하자면 어렵겠지만 코드를 손으로 예시를 들어서 하나씩 해보면 이해가 갈 것이다. 모르겠으면 댓글을 남겨주세여!