[실버1] 2293번 : 동전1

🛠 문제

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

👩🏻‍💻 해결 방법

dp를 사용해야 하는 건 알았는데 점화식을 세우는 것이 어려웠다(단순하게 생각할 문제가 아니었음...)
동전 단위를 하나씩 사용하면서 모든 금액에 해당 동전을 사용했을 경우를 dp에 축적해주었다

소스 코드

n, k = map(int, input().split())
c = []
for _ in range(n):
  c.append(int(input()))

dp = [0] * (k+1)
dp[0] = 1

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

print(dp[k])