백준 2839 풀이

n=int(input())
d= [5001]*5001
a=[3,5]
d[0]=0
for i in range(2):
    for j in range(a[i],n+1):
        d[j]=min(d[j],d[j-a[i]]+1)
if d[n]!=5001:
    print(d[n])
else:
    print(-1)

dp의 가장 기초적인 문제이자 그리디가 섞인 문제이다.

dp배열을 n의 최대범위 5000에다가 1을 더한 5001로 5001개 생성한다.

(최소값을 구하기 위한 5001과 최대 n이 5000일 수 있으니)

 

2번 for문을 돌린건 3,5 짜리 화폐 2개 일 경우들을 나타낸 것이고 그 안에

이중 포문은 어짜피 a[i]보다 작으면 나눠 떨어지지 않으므로 a[i]에서 n까지

범위를 설정해 준다. 포문안에 내용은 점화식을 그대로 표현한 것으로서, 

x원일때 x-3 혹은 x-5원일때 개수에 +1을 해준다.