[백준 2293] 동전 1 with Python

문제 링크

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

2293번: 동전 1

풀이

import sys

n, k = map(int, sys.stdin.readline().split())
coin = [int(sys.stdin.readline()) for _ in range(n)]
dp = [1]+[0]*k
for value in coin:
    for i in range(1, k+1):
        if i < value: continue
        dp[i] += dp[i-value]

print(dp[k])

dp[k]는 목표액 k원을 만드는 방법의 개수라고 할 때,

먼저 임의의 동전 하나로 k원을 만드는 개수로 dp를 채우고 난 뒤에

그 dp를 기반으로 다른 동전들을 사용했을 때의 개수로 dp를 갱신해 나갈 수 있다.

 

dp는 [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]으로 초기화하는데, 그 이유는

0번째 인덱스가 1인 이유는 0원을 만드는 방법은 동전을 하나도 사용하지 않는 경우 딱 1개 뿐이기 때문이다.

 

동전들의 가치를 모아놓은 배열 coin을 순회하면서

1~k의 목표액 중 현재 동전의 가치 이상인 목표액에 대해서 dp를 갱신한다.

목표액이 동전의 가치보다 낮으면 해당 동전을 사용할 수 없기 때문이다.

 

목표액이 동전의 가치 이상이라면 이제 해당 동전을 사용할 수 있다.

이 때, 동전을 1개 사용했을 때, 나머지 금액을 채우는 방법의 개수는 이미 dp에 저장되어 있다.

바로 dp[현재목표액 - 현재동전가치]가 현재 동전을 1개 사용했을 때 나머지 금액을 채우는 방법의 개수이다.

 

예를 들어 현재 동전이 3원짜리이고, 목표액 k는 10원이라면

dp[1], dp[2]는 목표액이 현재 동전 가치인 3원보다 작으므로 갱신되지 않아서 그대로 0이다.

dp[3]의 경우 현재 동전 1개를 쓰면 0원이 남는데 이 0원을 채우는 방법의 개수가 이미 dp[0]에 저장되어 있다.

따라서, dp[3] = dp[3] + dp[3-3] = dp[3] + dp[0]이 된다.

마찬가지로 dp[4]는 현재 동전 1개를 쓰면 1원이 남고, 이 1원을 채우는 방법의 개수가 dp[1]이므로,

dp[4] = dp[4] + dp[4-3] = dp[4] + dp[1]이 된다.

이런식으로 dp를 갱신하면

dp = [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0]이 된다.

 

마찬가지로 나머지 동전에 대해서도 현재 dp를 가지고 계속 갱신하면 된다.

예를 들어, 3원짜리 동전 외에도 4원과 5원 동전도 주어졌다고 하자.

이 상태에서 4원짜리 동전에 대해 dp를 갱신하면 이미 고려한 3원과 현재 동전인 4원 두 개 종류의 동전으로 목표액을 채우는 방법이 dp에 저장된다.

여기에 다시 5원짜리 동전에 대해 dp를 갱신하면, 3원, 4원, 5원 총 3개 종류의 동전으로 목표액을 채우는 방법이 dp에 저장된다.

따라서, 모든 종류의 동전에 대해 누적해서 dp를 갱신하면 모든 종류의 동전 사용을 고려했을 때의 목표액 k를 채우는 방법의 개수가 dp[k]에 저장된다.

---

ex) 문제 예시에 나온대로 1원, 2원, 5원 동전으로 목표액 10원을 만든다고 했을 때,

 

1원짜리 동전에 대해 갱신한 dp (= 1원짜리 동전만으로 각각의 목표액을 만드는 방법의 개수)

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

2원짜리 동전에 대해 갱신한 dp (= 1원과 2원짜리 두 종류의 동전으로 각각의 목표액을 만드는 방법의 개수)

[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]

5원짜리 동전에 대해 갱신한 dp (= 1원, 2원, 5원짜리 세 종류의 동전으로 각각의 목표액을 만드는 방법의 개수)

[1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10]

 

(동전의 순서가 바뀌어도 상관이 없다.)

dp[k] = 10 이므로, 1원, 2원, 5원짜리 동전으로 10원을 만드는 방법의 개수는 총 10개다.

 

---

※ 2021년 9월 10일 현재 이 문제는 메모리 제한 때문에 Node.js로 통과할 수 없는 상태이다.