[이코테] CH08 다이나믹 프로그래밍 실전문제 5번 효율적인 화폐 구성

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
N,M = map(int,sys.stdin.readline().split())
d = [10001] * (M+1)
coin = [0]
for _ in range(N):
    value = int(sys.stdin.readline().rstrip())
    coin.append(value)
    d[value] = 1

for i in range(1,M+1):
    for j in range(1,N+1):
        if d[i-coin[j]]!=10001:
            d[i] = min(d[i-coin[j]] + 1,d[i])

if d[M] == 10001:
    print(-1)
else:
    print(d[M])

혼자서 거의 다 풀어서 매우 기쁘다..

M값의 상한이 10000이므로 배열 전체를 10001로 초기화해주었다.

만약 d[i-coin[j]]가 10001이 아니라는것은 

조합을 할 수 있는 방법이 존재한다는 의미이므로

d[i]를 현재값과 d[i-coin[j]] 값과 비교해준다(더 큰 화폐가치를 사용했었다면 원래의 d[i] 값이 더 작을 수 있다)

 

조금은 뿌듯하지만

아직도 문제를 봤을 때 dp로 풀어야 할지 아닐지 딱 보이려면

너무 멀었다.. 지금은 dp 단원을 공부하고 있으니까 풀이법이 보이는거지만 

코테는 절대 단원명을 명시해주지 않는다

더 열심히 하자

파이팅