2294. 동전

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

 

✔ 유형 : DP

✔ 문제 풀이: 여러개의 하위 문제를 먼저 푼후 그 결과를 쌓아올려 주어진 문제를 해결한다.

 

메모- 처음에 DFS로 풀었는데, 메모리 초과나서 방법을 찾다가 DP를 공부하고 DP로 풀었다. 근데 이게 정답인듯!!!

 

DP 풀이

1. 테이블 정의

    D[i] = K 로 만들기 위해 필요한 연산 횟수의 최소값

 

2. 점화식

    D[15] = D[14] + 1  ( 1을 더한 이유는 D[15-1]에 1을 더하는 연산 한번을 더하면 D[15]이기 때문)

    D[15] = D[9] + 1  ( 1을 더한 이유는 D[15-6]에 5를 더하는 연산 한번을 더하면 D[15]이기 때문)

    D[15] = D[3] + 1  ( 1을 더한 이유는 D[15-11]에 11를 더하는 연산 한번을 더하면 D[15]이기 때문)

 

    일반화 하면

     D[K] = D[K- coinvalue] + 1

 

3. 초기값

    D[0] = 0

    0원이 되기 위한 최솟값은 0번면 된다.

 

 

 

⬇️ 풀이

import sys
from collections import deque
input = sys.stdin.readline

# 입력
n, k = map(int,input().split())

coins = set()

for _ in range(n):
    coins.add(int(input()))
    

dp = [1e9] * (k + 1)
        
dp[0] = 0


for i in range(1,k+1):
    for coin in coins:
        if i - coin >= 0 : 
            dp[i] = min(dp[i] , dp[i-coin] + 1) 
        
# 결과 출력
if dp[k] == 1e9:
    print(-1)  # k원을 만들 수 없는 경우
else:
    print(dp[k])
    
# 메모리 초과 개빡치네"?


# 참고문제
# https://www.acmicpc.net/problem/1463