[백준][DP] 2293. 동전 1

2293. 동전 1

2293번: 동전 1

 

• 풀이
  • num의 값들이 다 다르게 들어오므로 num하나하나 돌아가면서 넣기
  • 앞 값들이 미리 다 계산된 상태로 dp를 돌면 중복되는 부분이 발생
    • num의 값을 하나 돌때마다 전체를 돌면서 개별적으로 더해주기

https://mong9data.tistory.com/68 참고

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

dp=[0 for _ in range(k+1)]
dp[0]=1 #num에 2가 들어있는 경우 더해줘야하므로
for i in num:
    for j in range(k+1):
        if j-i<0: continue
        dp[j]+=dp[j-i]

print(dp[k])