스파르탄 365 5주차 (5) 동전2

참고사이트: 황소개발자

5주차

백준 2294번 동전2

문제링크 : https://www.acmicpc.net/problem/2294

💡 풀이 중 고민

• 점화식을 어떻게 세울 것인가
• 동전의 개수가 최소가 되어야하니 min을 사용하겠지?
• 언제의 개수와 비교해야 하는가
• 이걸 코인 배열과 어떻게 엮어서 생각하는가

해결방법

• 가능한 방법을 모두 나열해서 써본다.
• ex. 12원이면 코인 배열에 있는 코인을 뺀 경우와 본인을 비교
  dp[12-5]+1 , dp[12]
  

!! 스킬

print(dp[-1] if dp[-1] != 10001 else -1)

깨달음

• 예외 처리를 출력 부분에서 할 수도 있구나
• 점화식 세우는 연습을 더 할 것

풀이

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = [0] * n
dp = [10001] * (k+1)
dp[0] = 0
for i in range(n):
    coins[i] = int(input())

coins.sort()
for coin in coins:
    for i in range(coin, k+1):
        dp[i] = min(dp[i-coin]+1, dp[i])

print(dp[-1] if dp[-1] != 10001 else -1)