백준 설탕 배달 dp

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

2839번: 설탕 배달

 

설탕 배달은 DP와 그리드 방식으로 해결 가능합니다. 사실 시간이 적다면 그리드 방식이 좋을 수 있지만

해당 문제는 DP 문제로 분류되어있으니 DP 방식으로 풀도록 하겠습니다.

 

해당 문제의 점화식입니다.

min(dp[j], dp[j-arr[i]] +1)

 

해당 문제의 풀이입니다.

n = int(input())
arr = [3, 5]
dp = [5001]*(n+1)
dp[0] = 0

for i in range(len(arr)):
    for j in range(arr[i], n+1):
        if dp[j - arr[i]] != 5001:
            dp[j] = min(dp[j], dp[j-arr[i]] +1)
if dp[n] == 5001:
    print(-1)
else:
    print(dp[n])

동적 계획법 방식중에서도 다운 - 탑 방식을 선택했습니다.

DP의 크기는 N+1의 크기로 생성합니다.

DP의 0번째 인덱스의 값은 0으로 생성하고 나머지는 5001의 값을 넣습니다.

5001의 값을 넣은 이유는 5001 값이 가장 최고 값이 될 것이기 때문입니다.

설탕 봉투의 키로 수는 3KG, 5KG 가 있습니다.

따라서 작은 설탕 봉투 3KG를 먼저 DP에값을 채워 넣습니다.

그다음에 5KG 봉투를 채워 넣습니다.

5키로 봉투를 채워 넣을 때 만약 현재 인덱스가 8이면 

8에는 5001의 값이 들어가 있을 것입니다.

8일 때 DP [8-5]의 값을 확인할 것이고 확인된 값은 DP [3] = 1 일 것입니다.

값을 비교하게되면 min(5001, 2)가 될 것이고 2의 값이 들어가게 될 것입니다.

위와 같은 방식으로 해당 인덱스의 가장 작은 수가 값으로 들어올 것입니다.