백준 / 2293번 / 동전 1 / python 파이썬

 

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

 

 

평소 DP 문제들의 접근에 어려움을 느끼는데 점화식을 세우는 것이 어려운 것 같다. 

이번 문제도 점화식 아이디어가 떠오르지 않아서 검색을 통해 공부하고 접근법을 이해하는 데에 노력하였다.

단순히 코드를 보는 것만으로 이해가 어려울 때엔 유튜브로 해설 영상을 통해 보다 쉽게 이해할 수 있다.

 

 

 

 

정답 

n, k = map(int, input().split())

coins = [int(input()) for _ in range(n)]
coins.sort()

DP = [0] * (k + 1)
DP[0] = 1
for c in coins:
    for i in range(c, k + 1):
        DP[i] += DP[i - c]
print(DP[k])