[Python] 백준 2293 동전 1 - 다이나믹 프로그래밍 (DP)

백준 홈페이지 문제와 개인적인 풀이를 작성한 글입니다.

 

백준문제 - 2293 : 동전 1

2293번: 동전 1

 

---

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

입력

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

 

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

 

예제 입력 1	예제 출력 1
3 10 1 2 5	10

 

코드

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
coins = []

for i in range(n):
  coins.append(int(input()))

dp = [0] * 10001
dp[0] = 1

# 코인들 돌리기
for coin in coins:
  # 아래부터 놀려도 되는데, coin 아래에는 어짜피 값이 안들어가기 때문에 다음과 같이 처리
  for c in range(coin, k + 1):
    if c >= coin:
      dp[c] += dp[c - coin]

# 정답 출력
print(dp[k])

 

해설

동전 1 - 그림 1

코드를 토대로, 문제를 풀어보면 다음과 같다.

 

K = 5 이고, Coin 이 1 일 때

4 로 만들 수 있는 경우에 수를 모두 추가한다.

 

K = 5 이고, Coin 이 2 일 때

3 로 만들 수 있는 경우에 수를 모두 추가한다.

 

K = 5 이고, Coin 이 5 일 때

0 으로 만들 수 있는 경우에 수를 모두 추가한다.

다르게 말하면 하나 밖에 없습니다. (하여, 초반에 dp[0] = 1 을 설정합니다.)

 

모든 DP 문제의 경우에는 가장 헷갈리는 부분은 2가지로 보고 문제를 풀고 있습니다.

1. 중복을 고려해야 하는 경우
   이번 문제에서는 dp[4] 를 예시로 들어보겠습니다. 4로 되는 경우가 1 + 1  + 2 와 2 + 1 + 1 은 동일한 경우의 수로 판단하고 문제를 풀어야 합니다.
2. 두번째 이중 for 문에서의 범위 설정
   위에서 주석으로 단 것 처럼, coin 의 숫자부터 시작하고 있다. 불필요한 작업을 지우기 위해서 입니다.