알고리즘/백준

2839번: 설탕 배달

happenundo 2023. 2. 20. 16:09
728x90
 

2839번: 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그

www.acmicpc.net

그리디 또는 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)
728x90