https://www.acmicpc.net/problem/2294
이거 어캐품.
실버 상위권만 되도 응용이 필요하네.. 하
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
coin=[]
for i in range(n):
coin.append(int(input()))
d=[0]*100
result=[]
for j in coin:
for i in range(1,100):
if i%j==0:
d[i]=i//j
for j in coin:
for i in range(1,100):
if i-j>0:
d[i]=min(d[i],d[i-j]+1)
if d[k]:
print(d[k])
else:
print(-1)
O(nk) 그냥 dp[i]를 i 만드는데 드는 최소개수라 하고 각각 i에 대해 dp[i+a[i]]를 업데이트하면 될거같음
a[i]가 동전임? 업데이트하면 모든 동전을 조합했을 때 제일 최소 갯수가 나옴? 어떻게 되는건데
ㅇㅇ a[i]가 각각 동전의 가치(1<=i<=n)이라 할때, dp[0] = 0이고 이외의 dp[x]=INF로 초기화해두고 모든 0<=x<=10000에 대해 x가 증가하는 순서대로 dp[x+a[i]]=min(dp[x+a[i]], dp[x]+1)을 해주면 항상 dp[x]는 x 가치를 만드는데 필요한 최소 동전 개수가 됨. 증명은 수학적 귀납법으로 될거같은데
내가 짠 코드 올려놨는데 틀림. 왜 틀린거지?
일단 d를 min update할거니 0이 아니라 INF로 초기화해야하고, 업데이트 순서가 i에 대해 모든 동전을 봐야하니 i 안에 j가 와야하고, 그리고 d 길이가 너무 작음 (k<=10000)
ㄳㄳ
j안에 i가 와도 상관은 없긴한듯