문제

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

point

DP

• c[i] : i번째 동전 가격
• D(i, k) : 1번 ~ i번 동전 사용하여 k원을 만드는 경우의 수
• dp 초기값
  : dp[0] = 1 _ 동전을 사용하지 않고 0원을 만드는 경우
  : 나머지 = 0
  

점화식

• D(i, k)
  • [ 1번 ~ (i-1)번 동전을 사용하여 (i번 동전을 사용하지 않고) k원을 만드는 경우의 수 ] + [ i번 동전을 무조건 사용하여 k원을 만드는 경우의 수 ]
  • i번 동전을 무조건 사용하여 k원을 만드는 경우의 수
    = 1번 ~ i번 동전을 자유롭게 사용하여 k-c[i]원을 만드는 경우의 수
    : k-c[i]원 만드는 모든 경우의 수에 제일 앞에 i원짜리 동전을 붙이는 경우
  • ex. 9원
    • 5원짜리 무조건 쓴 경우의 수 = 3
      
    • 9원을 [1,2] 동전만으로 구성 경우의 수 + 3

전체코드

n, k = [int(x) for x in input().split()]
coins = []
for i in range(n):
  coins.append(int(input()))
  
dp = [0]*(k+1)
dp[0] = 1

def step(c):
  global dp, k
  i = 0
  for i in range(k+1):
    if i-c < 0:
      continue
    dp[i] += dp[i-c]

for c in coins:
  step(c)
  
print(dp[k])

referenced

• https://debuglog.tistory.com/78