[백준] 2839 설탕 배달(Python)

백준 - 2839 설탕 배달

풀이

봉지가 3키로 or 5키로 -> 5가 3의 배수가 아니기때문에 그리디로 해결할 수 없음
➡️ dp로 해결

1. 큐와 dp를 이용해서 해결하려고 했다.
   큐에 초기값으로 3, 5를 넣어두고 while문을 돌면서 큐에서 하나씩 빼서 각 자리수를 비교하고자 했다.
   처참히 실패 (시간초과)

2. 큐를 없애버리고 dp를 구현했다. 경우의 수를 나눠서 계산했다.
   n=9인 경우를 예로 들어보자.

# dp 초기값
       0   1   2  3   4  5   6   7   8   9
dp = [-1, -1, -1, 1, -1, 1, -1, -1, -1, -1]

for i in range(6, n + 1):
    if dp[i - 3] > 0 and dp[i - 5] > 0:
    	# i = 8인 경우 
        # dp[5] = 1, dp[3] = 1 이므로 둘 중 최소값에 + 1을 저장해야함
        # (5kg 경우의 수 + 3kg) vs (3kg 경우의 수 + 5kg)
        # -> 둘 중에 작은 값을 골라야 함 => min()
        dp[i] = min(dp[i - 3], dp[i - 5]) + 1
    elif dp[i - 3] < 0 and dp[i - 5] < 0:
    	# i = 7인 경우 
        # dp[4] = -1, dp[2] = -1
        # (4kg 경우의 수 = x, 2kg 경우의 수 x) -> 4kg나 2kg에서 3kg 혹은 5kg를 옮길 수 없음
        dp[i] = -1
    else:
    	# i = 6인 경우
        # dp[3] = 1, dp[1] = -1
        # (3kg 경우의 수 + 3kg) vs (1kg 경우의 수 + 5kg = x(옮길 수 없음))
        # -> 3kg 경우의 수 + 3kg => 둘 중에 큰 값임 => max()
        dp[i] = max(dp[i - 3], dp[i - 5]) + 1
        
print(dp[n])

코드

1. 통과한 풀이 (dp)

n = int(input())
dp = [-1] * (max(n, 5) + 1)
dp[3] = dp[5] = 1

for i in range(6, n + 1):
    if dp[i - 3] > 0 and dp[i - 5] > 0:
        dp[i] = min(dp[i - 3], dp[i - 5]) + 1
    elif dp[i - 3] < 0 and dp[i - 5] < 0:
        dp[i] = -1
    else:
        dp[i] = max(dp[i - 3], dp[i - 5]) + 1
        
print(dp[n])

2. queue + dp -> 시간초과 ㅠ

from collections import deque

n = int(input())
MAX = n + 1
answer = [MAX] * (max(n, 5) + 1)
answer[3] = answer[5] = 1

queue = deque([3, 5])

while queue:
    kg = queue.popleft()
    answer[kg] = min(answer[kg], answer[kg-3]+1, answer[kg-5]+1)
    if kg+3 <= n:
        queue.append(kg+3)
    if kg+5 <= n:
        queue.append(kg+5)

print(answer[n] if answer[n] != MAX else -1)