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

• 그리디 알고리즘
  • 현재의 최적해를 선택
  • 단, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
  • 따라서, 부분 최적의 합이 반드시 전체 최적해는 아닐 수 있음
• 시간 복잡도
  • N, NlogN

• 부분 최적의 합이 전체 최적해를 보장한다면, 최적해를 구할 수 있음
• 여기서 결국 DP로도 접근이 가능해짐

• 포장할 수 없을 경우 -1로 출력
• 최소한의 포장지를 사용하려면, 가능한 5kg를 많이 사용하여 포장

n = int(input())
result = -1

for five_kg in range(n//5, -1, -1):
    remaining = n - (five_kg * 5)
    
    if remaining % 3 ==0:
        result = five_kg + (remaining // 3)
        break

print(result)

n = int(input())
dp = [5001] * (n + 1)
dp[0] = 0

# 점화식 dp[i] = min(dp[i-3]+1, dp[i-5]+1)
for i in range(3, n+1):
    if i >= 3:
       dp[i] = min(dp[i], dp[i-3] + 1)
    
    if i >= 5:
        dp[i] = min(dp[i], dp[i-5] + 1)
        
        
if dp[n] == 5001:
    print(-1)
else:
    print(dp[n])