[백준] 2293번: 동전 1 (파이썬)

✅문제: 2293번

📌문제풀이

주어진 동전들로 특정 금액을 만드는 경우의 수를 구하는 문제임. 각 동전은 무한히 사용할 수 있으며, 동전의 종류와 목표 금액이 주어짐.

1. DP 테이블 초기화
   • dp[x]: 금액 x를 만드는 경우의 수를 저장하는 배열
   • dp[0] = 1: 금액 0을 만드는 방법은 아무 동전도 사용하지 않는 1가지 경우뿐임.
2. 동전 업데이트
   • 각 동전에 대해 해당 동전을 포함하여 만들 수 있는 금액을 계산함.
   • 현재 금액 x에서 dp[x] += dp[x−coin] 으로 이전 값에 추가함.
     • 즉, 동전 coin을 사용해 금액 x를 만드는 경우의 수를 누적함.
3. 결과 출력
   • DP 테이블에서 dp[k] 값을 출력하여 금액 k를 만드는 경우의 수를 반환함.

import sys
input = sys.stdin.read

def solution(coins, k):
    dp = [0] * (k + 1)
    dp[0] = 1

    for coin in coins:
        for amount in range(coin, k + 1):
            dp[amount] += dp[amount - coin]
    
    return dp[k]

data = input().split()
n = int(data[0])
k = int(data[1])
coins = list(map(int, data[2:]))

result = solution(coins, k)
print(result)

위 코드를 예제 입출력 과정을 이해하려면 아래와 같이 확인할 수 있음.

# 예제 입력 1
3 10
1
2
5

1. DP 테이블 초기화
   • 초기 상태: dp = [1,0,0,0,0,0,0,0,0,0,0]
2. 1원 동전 업데이트
   • 금액별 경우의 수 계산: dp[x] += dp[x−1]
   • 결과: dp = [1,1,1,1,1,1,1,1,1,1,1]
3. 2원 동전 업데이트
   • dp[x] += dp[x−2]
   • 결과: dp = [1,1,2,2,3,3,4,4,5,5,6]
4. 5원 동전 업데이트
   • dp[x] += dp[x−5]
   • 결과: dp = [1,1,2,2,3,4,5,6,7,8,10]
5. 결과 출력
   • dp[10] = 10

# 예제 출력 1
10

📌후기

• 동적 계획법(DP)을 활용해 문제를 푸는 문제인데, DP에 대해서 공부하고 나서 풀면 골드 4치고는 풀만한 것 같음.
• 중복 계산을 피하면서 모든 동전 조합을 고려하는 방법에 대해서 알 수 있었음.