[Python] BOJ / 2293번 / 동전 1

2293번: 동전 1

 

📝 문제

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

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

 

📜 풀이

• 문제에 제시된 예시를 기준으로 각 동전을 사용했을 때 i(1 ~ 10)원이 되는 경우의 수를 구해보면 아래와 같음

• 동전의 가치가 i보다 큰 경우에는 애초에 그 동전을 경우의 수에 포함시킬 수 없으므로, 해당 동전을 사용하기 이전의 경우의 수와 같다.
• 동전의 가치가 i보다 작거나 같은 경우에는 (해당 동전을 사용하기 이전의 경우의 수) + (i원에서 해당 동전의 가치를 뺀 가치의 합이 되는 경우의 수)와 같다.
  • 풀어서 쓰다보니까 알아듣기 힘들게 설명되었는데, 예시로 1, 2원짜리 동전에서 5원짜리 동전을 추가하여 6원을 만드는 경우의 수는 (1, 2원으로 6원을 만드는 경우의 수) + (1, 2, 5원으로 1(6 - 5)원을 만드는 경우의 수)인 것이다.
• 다만 이를 2차원 배열의 형태로 구현하여 풀기에는 문제의 메모리 제한을 고려했을때 힘들다고 판단했으며, 이를 해결하기 위해 1차원 배열상에서 값을 교체하는 방식으로 구현하였다.
• 추가로, 다른 DP 문제와 다르게 DP 배열의 0번째 값을 '0'이 아닌 '1'로 설정한 이유는 동전이 딱 하나만 사용될 때 DP[0]의 값을 이용하기 위해서이다.
  • ex) 1, 2원으로 2원을 만드는 경우 / 1, 2, 5원으로 5원을 만드는 경우

 

💻 소스코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coin = [int(input()) for _ in range(n)]
dp = [1] + [0] * k

for i in coin:
    for j in range(1, k + 1):
        if i <= j:  # j - i >= 0
            dp[j] = dp[j] + dp[j - i]
print(dp[k])