[BOJ] DP - 2839 설탕 배달

www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

import sys

n = int(sys.stdin.readline().rstrip())

# 정확하개 N kg을 만들 수 없는 경우
result = -1
# 5 kg 봉지의 수
count_five = 0

while True:
    # 현재 필요한 설탕
    current = n
    # 5 kg 봉지로 담은 후 남은 설탕
    current -= count_five * 5

    # 더 이상 남아 있는 설탕이 없는 경우 종료
    if current < 0:
        break

    # 3 kg 봉지로 설탕을 정확하게 담을 수 있는 경우
    if current % 3 == 0:
        # 봉지 최소 개수
        if result == -1 or result > count_five + current // 3:
            result = count_five + current // 3

    # 5 kg 봉지 수를 한 개 늘려 다시 계산
    count_five += 1

print(result)