[백준] DP - 동전1

동적계획법(Dynamic Programming) 문제 풀 때 확인하기

1. 전체 -> 부분 문제로 나누었는가?

2. 부분 문제를 해결한 후의 결과를 메모이제이션 하는가?

 

www.acmicpc.net/problem/2293

2293번: 동전 1

import sys

n, k = map(int, sys.stdin.readline().split())
coin = []
for _ in range(n):
    coin.append(int(sys.stdin.readline()))

dp = [0] * (k + 1)
dp[0] = 1
for i in range(n):
    for j in range(coin[i], k + 1):
        dp[j] += dp[j - coin[i]]

print(dp[k])

 

동전 문제를 보다가 블로그 글들을 봐도 이해가 잘 되지 않았다.

유튜브를 찾다가 정말 이해가 확! 되는 영상을 찾았다.

저처럼 이해 안되시는 분들은 아래 유튜브 영상 참고해보세요 :)

www.youtube.com/watch?v=2IkdAk1Loek