[백준] DP - 동전1

알고리즘/[문제풀이] 백준

[백준] DP - 동전1

로그뉴 2020. 10. 4. 15:52

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

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

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

www.acmicpc.net/problem/2293

2293번: 동전 1

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

www.acmicpc.net

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])

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

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

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