BOJ백준 2293 동전1 풀이(Python)

문제 링크

n가지 종류의 동전을 이용하여 k원을 만드는 경우의 수를 구하는 문제이다.

이 문제역시 Dynamic Programming을 이용하여 간단히 해결할 수 있다.

개인적으로 DP문제의 핵심은 문제를 어떻게 작은 문제로 나누거나 일반화시킬 것인가이기 때문에

이와 같은 관점에서 생각해본문제 풀이의 핵심 전략은 다음과 같다.

A-k1원, A-k2원, A-k3원...까지 주어진 동전들로 만드는 경우를 구했다고 했을 때 A원을 만드는 경우는 다음의 경우들을 더해주면 된다.

더 자세히 서술하면

1. n가지 종류의 동전을 반복문으로 순회하면서 내부에서 반복문을 한 차례 더 돌린다.

2. 이 때 내부 반복문은 동전의 가치부터 k까지 순회한다.

3. 내부 반복문이 j번째를 순회한다고 했을 때 dp[j]에 dp[j-(순회중인 동전의 가치)]의 값을 더해준다.

예를 들어 3, 6의 가치를 가진 동전이 있다고 했을 때의 흐름은 다음과 같다.

3원일 때 : 3부터 시작 -> dp[3] += dp[3 - 3] (동전을 처음 하나만 쓸 때를 위해 dp[0]에 1을 미리 넣어둔다.)

dp[4] += dp[4 - 3]

dp[5] += dp[5 - 3]

dp[6] += dp[6 - 3]

   .

   .

   .

6원일 때 : 6부터 시작 -> dp[6] += dp[6 - 6] (위에서 계산했었던 3원으로 6원을 만드는 dp[6]값에 6원으로 6원을 만드는 이번 경우가 더해진다.)

dp[7] += dp[7 - 6]

   .

   .

   .

이렇듯 이전에 구했던 값들에 현재 경우들을 더해주면서 

이렇게 각 동전별로의 경우를 차례대로 더해주면서 k까지 모두 순회했을 때 dp[k]값이 찾는 답이 된다.

아래는 소스코드이다.

import sys
 
n, k = list(map(int, sys.stdin.readline().split()))
value = []
for i in range(n):
    temp = int(sys.stdin.readline())
    value.append(temp)
 
dp = [0 for i in range(10001)]
dp[0] = 1
for i in value:
    for j in range(i, k+1):
        dp[j] += dp[j-i]
 
print(dp[k])
# 해결

비판 및 조언은 언제나 환영입니다. :)