[Python] 백준 알고리즘 #2839 설탕 배달

문제풀이

 

DP(Dynamic Programming) 문제이다.  DP는 큰 문제를 해결하기 어려울 때 앞의 작은 경우를 나누어서 해결하는 기법이다.

 

문제를 해결하다보면 작은 문제와 겹치는 부분을 다시 계산하지 않고 저장했다가 재사용하면 큰 문제를 해결할 때 훨씬 더 효율적으로 계산할 수 있다. 

 

설탕 배달과 같은 문제는 먼저 작은 문제들의 경우를 DP 리스트로 저장하여 준다. 

 

3kg, 5kg 일경우 각각 1이며 0~2,4의 경우는 0가지이다. 

 

DP 리스트로 저장하였을 때, 다음과 같이 저장한다. DP = [0,0,0,1,0,1]

 

이제 더 큰 경우를 구하려면 DP 점화식을 세워야 한다. 

 

	1	2	3	4	5	6	7	8	9	10
3	0	0	1	0	0	2	0	1	3	0
5	0	0	0	0	1	0	0	1	0	2
총	0	0	1	0	1	2	0	2	3	2

 

	11	12	13	14	15	16	17	18	19	20
3	2	4	1	3	0	2	4	1	3	0
5	1	0	2	1	3	2	1	3	2	4

20까지 규칙을 보았을 때, DP[n] 의 값은 DP[n-3]+1 과 DP[n-5]+1 중 작은 값이다. 다음을 점화식으로 나타내면,

 

DP[n] = min(DP[n-3],DP[n-5])+1 이다.

 

하지만 1,2,4,7 인덱스의 값이 0인데 이는 없는 경우 이므로 포함되어서는 안 되니 N의 최댓값 5000을 넣어준다. 

 

 

소스코드

import sys
input = sys.stdin.readline

n = int(input())

dp = [5000,5000,5000,1,5000,1,2,5000] 
if n<=7:
    if n==3 or n==5 or n==6:
        print(dp[n])
    else:
        print(-1)
    exit()
for i in range(8,n+1):
    temp = min(dp[i-3], dp[i-5])
    dp.append(temp+1)
if dp[n]>=5000:
    print(-1)
else:
    print(dp[n])

 

www.acmicpc.net/problem/2839

2839번: 설탕 배달