[BOJ] 다이나믹 프로그래밍/그리디 : 설탕 배달(2839) ★

아이디어

• 3킬로 또는 5킬로 봉지만 활용
• 주어지는 설탕의양(n)을 가장 적은 봉지 수로 처리
• 5킬로 봉지만으로 구성할 수 있는지 확인
• 5킬로 봉지를 최대로 활용했을 때 3킬로로 나누어 떨어지는지 확인

코드(성공)

n = int(input())
answer = -1
if n % 5 == 0:
    answer = n//5
else:
    mx = n // 5
    for i in range(mx, -1, -1):
        if (n - (5 * i)) % 3 == 0:
            answer = i + ((n - (5 * i)) // 3)
            break
print(answer)

고찰

• 설탕을 담을 수 있는 봉지가 5킬로와 3킬로 뿐이어서 해결되었지만, 만약 봉지의 수가 여러개인 경우 복잡해진다.
• 따라서 다이나믹 프로그래밍으로(메모이제이션) 해결하는 것이 더 나은 방법으로 생각된다.