2839번: 설탕 배달

2839번: 설탕 배달

그리디 또는 DP로 풀 수 있는 문제다.

 

1. 그리디

n = int(input())

total = 0
while True:
    if n % 5 == 0:
        total += n // 5
        print(total)
        break
    elif n % 5 != 0:
        total += 1
        n -= 3

    if n < 0:
        print(-1)
        break

 

 

 

2. DP

n = int(input())

dp = [5001] * 5001

dp[3] = 1
dp[5] = 1

for i in range(6, n+1):
    dp[i] = min(dp[i-3], dp[i-5]) + 1

print(dp[n] if dp[n] < 5001 else -1)