백준 2293(파이썬) - 동전1

www.acmicpc.net/problem/2293

2293번: 동전 1

DP가 진짜 생각하기가 어려운거같다...

그림을 그려서 생각하다가 시간이 굉장히 오래걸렸다.

일단 테스트 케이스는 맞는데 계속 인덱스 에러가 나서 코드를 수정하다가 참고한 유튜브 영상이 있다.

DP는 많이 풀어봐야 할 거 같다.

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

#dp 보텀업방식 사용
n,k = map(int,input().split())
numbers = []
dp = [0 for _ in range(k+1)] #dp만들어주기
for _ in range(n):  
    numbers.append(int(input()))
dp[0] = 1 #처음에 1로 채워주고
for i in numbers:
    for j in range(i,k+1):
            dp[j] += dp[j-i]

print(dp[k])