[python] 백준 2293번 동전 1

백준 2293번 동전 1

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

문제

풀이

예시)
동전 종류: 1,2,5
목표 금액: 10

금액 10을 주어진 동전 종류로 만들 수 있는 방법:

• 1을 10번 사용하기
• 2를 5번 사용하기
• 5를 2번 사용하기
• 2를 1번 사용하고, 1 을 8번 사용하기... 등 총 10가지 방법이 있다.

dp[i] 는 금액 i를 만들 수 있는 경우의 수를 의미한다.
dp[0] = 1이 된다. 왜냐하면 0원을 만드는 방법은 동전을 사용하지 않는 1가지 방법 밖에 없기 때문이다.

그렇다면 동전 종류를 업데이트 해보자.
동전 1만 주어졌을 때,
dp[1] += dp[1 - 1] -> dp[1] = 1
dp[2] += dp[2 - 1] -> dp[2] = 1
dp[3] += dp[3 - 1] -> dp[3] = 1
dp[4] += dp[4 - 1] -> dp[4] = 1
...
dp[10] += dp[10 - 1] -> dp[10] = 1
어떤 금액이든 1가지 밖에 없다.

그렇다면 동전 2도 주어지면 어떻게 될까?
dp[2] += dp[2 - 2] -> dp[2] = 2
dp[3] += dp[3 - 2] -> dp[3] = 2
dp[4] += dp[4 - 2] -> dp[4] = 3
dp[5] += dp[5 - 2] -> dp[5] = 3
1원 5개, 2원 2개와 1원 1개, 2원 1개와 1원 3개
...
dp[10] += dp[10 - 2] -> dp[10] = 6

핵심은 dp[i] 는 금액 i를 만들 수 있는 모든 방법의 경우의 수이고, dp[i] 는 dp[i - 동전의 가치]를 통해 현재 동전을 사용하는 경우의 수를 추가하는 것이다.

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]

# DP 테이블 초기화
dp = [0] * (k + 1)
dp[0] = 1  # 0원을 만드는 방법은 1가지 (아무 동전도 사용하지 않는 경우)

# 동전 순회
for coin in coins:
    for i in range(coin, k + 1):
        dp[i] += dp[i - coin]

# 결과 출력
print(dp[k])

📌 주의

동전의 순서는 고려하지 않으므로, 각 동전으로 만들 수 있는 모든 금액을 DP 테이블에 누적한다.
각 동전에 대해 목표 금액 k까지 순회하므로, 시간 복잡도는 O(n * k)가 된다.