백준 2294 동전 2 파이썬 풀이

난이도 : 골드5

풀이일 : 2404066

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

2294번: 동전 2

---

문제

---

풀이코드

import sys

n, k = map(int, sys.stdin.readline().split())
coins = []
dp = [float('inf')] * (k + 1)  # 초기값 무한
dp[0] = 0  # 0 만드는 동전 개수

for _ in range(n):
    coins.append(int(sys.stdin.readline()))

# 각 coin에 대해 coin부터 k + 1까지
# dp[i], dp[i - coin] + 1 중 작은 값 저장
for coin in coins:
    for i in range(coin, k + 1):
        dp[i] = min(dp[i], dp[i - coin] + 1)

# 가지고 있는 동전으로 만들 수 있다면 최소 개수 출력
print(dp[k] if dp[k] < float('inf') else -1)

• coins : 가지고 있는 동전 종류를 저장하는 배열입니다.
• dp : 인덱스 값을 만들 수 있는 최소 동전 개수를 저장할 배열입니다. min()을 사용하기 위해, 최초 값은 float('inf')를 사용하여 무한대로 설정해줍니다.
• dp[0] : 0 값을 만드는 동전의 최소 개수는 0개 이므로 dp[0]을 초기화해줍니다.
• 동전을 입력 받아 coins에 저장해줍니다.

 

for coin in coins:
    for i in range(coin, k + 1):
        dp[i] = min(dp[i], dp[i - coin] + 1)
        
print(dp[k] if dp[k] < float('inf') else -1)

• 각 동전마다 동전 값부터 k + 1 까지 반복하며 dp를 계산합니다.
• dp[i]에 현재 저장되어 있는 값과, 이 코인이 추가될 수 있는 이전 값에 현재 코인 개수를 더한 값 dp[i - coin] + 1 중 작은 값을 dp[i]에 저장합니다.
• 최종적으로 무한대 값이 저장되어 있다면, 가지고 있는 동전으로 해당 값을 만들 수 없으므로, -1을 출력합니다.
• 무한대 값이 아닌 값이 저장되어 있다면, 저장된 값을 출력합니다.

---

느낀점

• 이런 유형의 dp 문제를 연달아 풀어보니 조금 익숙해지는 것 같다. 다른 유형의 dp 문제도 풀어보면서 더 익숙해지도록 해봐야지