[Python]동적계획법2 백준 2293

   문제

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

다시 DP문제이다.

메모리 제한이 있긴하지만 크게 문제되지 않을거같다.

동전의 가치가 10만까지라면 0.4MB 정도 소모될것이다.

방법은 간단하다. 동전의 가치만큼의 크기를 가진 배열을 만들고 각 동전마다 만들수 있

는 가치를 구해준다.

각 코인마다 이전에 만들수 있던 가치를 받아와서 더해준다.

설명보다는 코드를 보고 조금만 생각해보면 이해할수 있을것이다.

import sys
 
input=sys.stdin.readline
n,k=map(int,input().split())
coin_list=[]
for i in range(n):
    coin_list.append(int(input()))
 
result=[0 for _ in range(k+1)]
result[0]=1#해당 동전을 한개만 사용했을때 값을 추가하기위해
 
for i in coin_list:#각 코인마다
    for j in range(i,k+1):#이전에 만들수 있었던 가치에 있던 배열의 값을 받아와 해당 코인의 가치를 더해 배열에 넣어준다.
        result[j]+=result[j-i]
 
print(result[k])