2839번: 설탕 배달

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

 

DP 문제 생각하는 게 어려워서 쉬운 문제부터 풀면서 감각을 익혀보고자 했다.

 

아이디어

 

'최솟값'을 찾아야 하므로, 최댓값보다 1 큰 5001로 dp 배열을 생성한다.

 

5로 나누어 떨어지면 dp[i]를 i // 5값으로

3으로 나누어 떨어지면 dp[i]를 i // 3 값으로 지정한다.

 

이후 현재 dp[i]값과 dp[i - 5] + 1값, dp[i - 3] + 1값과 비교한다.

(+1을 해주는 이유는 만약 지금 5나 3으로 나누어지거나 구성할 수 있다면, 이전 dp[i - 5] 혹은 dp[i - 3]일 때보다 1개 많은 설탕 봉지를 갖고 있기 때문이다.)

 

그렇게 해서 목표인 dp[N] 값이 5001보다 작다면 최종 값을 출력하고,

그렇지 않다면 -1을 출력한다.

# https://www.acmicpc.net/problem/2839
N = int(input())

dp = [5001] * (N+1)

for i in range(3, N+1) :
    if i % 5 == 0 :
        dp[i] = i // 5
    elif i % 3 == 0 :
        dp[i] = i // 3
    dp[i] = min(dp[i], dp[i - 5] + 1, dp[i - 3] + 1)

if dp[i] < 5001 :
    print(dp[i])
else : print(-1)