(Python) 백준 2839번 - 설탕 배달

문제 링크 : https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

풀이

처음엔 그리디 알고리즘으로 접근하려다가, 문제에서 제시된 봉지의 용량이 3kg , 5kg으로 배수의 관계가 아니기 때문에 불가능함을 깨닫고 다이나믹 프로그래밍으로 풀이를 진행했다.

import sys
n = int(sys.stdin.readline())
arr = [5001] * (n+1) # 문제에서 주어지는 최대 무게가 5000kg이므로 만들 수 없는 경우를 5001로 설정
arr[0] = 0 # 0kg은 봉지 없이 만들 수 있음
for i in range(3, n+1): # 1kg, 2kg은 만들 수 없기 때문에 계산하지 않음 
    if i == (3 or 5): # 3kg과 5kg은 봉지 한 개로 만들 수 있음
        arr[i] = 1
    elif i == 4: # 4kg은 만들 수 없으므로 5001 유지
        continue
    else: # 그 외의 수 계산
        arr[i] = min(arr[i], arr[i-3]+1, arr[i-5]+1)
if arr[n] == 5001: # 정확하게 만들 수 없는 경우
    print('-1')
else:
    print(arr[n])