[백준] 2839 설탕배달

실4

1. 문제

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

2839번: 설탕 배달

 

2. 풀이

 

실버 수준의 그리디/DP 문제이다.

 

예전에 그리디하게는 풀었었는데, DP로도 풀고 싶어서 다시 풀었다!!

 

1) Greedy 방법

 

1-1) 우선 그리디하게 풀어야하니까, 현재상황에서 가장 최선이도록 욕심을 부려야한다 == 5키로를 최대한 들자 !

1-2) 따라서 간단하다. 현재 주어진 숫자에 5로 나눠서 나눠지면 바로, 아니면 3씩 줄여가면서 5의 배수를 찾아가는지 해보면된다. 마지막까지 없으면 -1 출력.

 

## code ##

import sys

N = int(sys.stdin.readline())
cnt = 0
while True:
    if N < 3 and N > 0:
        print(-1)
        break
    if N % 5 == 0:
        cnt += N // 5
        print(cnt)
        break
    else:
        N -= 3
        cnt += 1

 

2) Dynamic Programming - Top Down 방식, 태뷸레이션

 

dp 라는 저장용 리스트를 선언해서 밑부터 채워가면서 올라가서 정답에 도달하는 방식이다.

2-1) 처음엔 모든 리스트에 -1로 초기화를 하고, dp[3], dp[5] = 1로 설정한다.

2-2) 점화식을 세워야하는데, 생각을 해보자.
설탕 배달에는 3과 5키로만 쓰인다. 그 즉슨, 이전 무게에 3을 올리거나 5를 올리면서 현재 무게에 맞는 개수를 찾는건데, 그중에서도 최소를 찾는다. 그러면 min( dp [ n - 3 ], dp [ n - 5 ] ) 이고, 여기에 +1을 해서 현재 무게까지 맞추도록 하면 되는거다 !!
따라서 점화식은 dp[n] = min(dp[n-3], dp[n-5]) + 1 !!!!

2-3) 근데 이게 3, 5 이후에도 -1인 친구들이 있는데, 7, 8같은 애들이고 또  6은 3 두개로 되니까 애매하다. 그래서 만약 7, 8 이런 숫자들 잘못 걸리면 -1로 min 계산 해야해서 중간에 꼬여버린다.
그래서 코드 상에서 만약 n-3 , n-5 값들이 -1인 경우 가지고도 조작을 해줘야 정답이 나온다.

 

## code ##

import sys

N = int(sys.stdin.readline())

def dynamic(i):
    dp = [-1] * (i+5)
    dp[3]=dp[5]=1

    for n in range(6, i+1):
        A = dp[n-3]
        B = dp[n-5]

        if A < 0 and B < 0:
            dp[n] = -1
        elif B<0:
            dp[n] = 1 + A
        elif A<0:
            dp[n] = 1 + B
        else:
            dp[n] = 1 + min(A, B)
    return dp[i]

print(dynamic(N))