[Python/Gold4/2293] 동전 1

|    문제

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

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

|    입력

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

|    출력

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

 

 

---

정답 코드

import sys
input = sys.stdin.readline

class Solution:
    def coins(self):
        n, k = map(int, input().split())
        coin = [int(input()) for _ in range(n)]
        dp = [0]*(k+1)
        dp[0] = 1 # 동전 없이 0원을 만드는 경우의 수
        for c in coin:
            for i in range(c, k+1):
                dp[i] = dp[i] + dp[i-c]
        print(dp[k])


if __name__ == "__main__":
     s = Solution()
     s.coins()

 

 

|    비고

배낭 문제와 비슷하다고 생각했는데 gpt 말로는 무한 배낭 문제라고 한다. 처음엔 점화식이 너무 이해가 안되어 배낭 문제에 대해 계속 찾아보았다. 결론적으로 가장 중요한 아이디어는 dp[i] = dp[i] + dp[i-c] 이다.

 

dp[i-c]가 의미하는 것

우리가 동전 c원을 만든다고 가정 -> 그러면 i원을 만드는 방법은 (i-c)원을 만들고 거기에 c원을 추가하는 방법

즉, dp[i-c]는 (i-c)을 만들 수 있는 경우의 수

 

dp[i] = dp[i] + dp[i-c]가 의미하는 것

dp[i]는 기존에 i원을 만들 수 있는 방법의 개수를 유지해야 함.

여기에 새로운 방법을 추가해야 하는데, (i-c)원을 만드는 방법에 각각 c원을 추가한다고 생각하면 새로운 방법이 생김.

바로 이 말이 바로 이해가 되질 않았는데, 예를 들어 1, 2원으로 4원을 만든다고 해보자.

 

1원만 사용할 때는 dp[i]는 모두 1이 될 것이고,

2원을 사용할 때부터가 중요한데,

✅ dp[i] = dp[i] + dp[i - 2]

• dp[2] = dp[2] + dp[2-2] = 1 + 1 = 2
  • 기존 방법 {1+1}
  • 새로운 방법 {2+(0)}
• dp[3] = dp[3] + dp[3-2] = 1 + 1 = 2
  • 기존 방법 {1+1+1}
  • 새로운 방법 {2+1}
• dp[4] = dp[4] + dp[4-2] = 1 + 2 = 3
  • 기존 방법 {1+1+1+1}
  • 새로운 방법 {2+1+1}, {2+2}

✅ 최종 dp 상태

dp = [1, 1, 2, 2, 3]

 

굵은 글씨 위주로 보면, 4원을 만드는 방법의 수는 기존의 1원으로만 4원을 만들었던 방법(1+1+1+1)에 새롭게 2원을 포함한 방법의 수를 더하면 된다. 이는 1원으로 2원을 만드는 방법에 2를 추가한 방법으로 기존 dp[2]가 (1+1, 2)의 방법이었다면 여기에 2원을 추가한 (1+1+2, 2+2)가 2원을 추가하여 4를 만드는 새로운 방법이며, 기존의 방법과 더하면 1,2원을 가지고 4원을 가지는 총 경우의 수3(1+1+1+1, 1+1+2, 2+2)을 구할 수 있게 된다.