2839 - 설탕 배달

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

2839번: 설탕 배달

import sys
input = sys.stdin.readline

n = int(input())
var1 = n // 5
var2 = n % 5

if not var2:
    print(var1)
else:
    while True:
        if (n-5*var1) % 3 == 0:
            print(var1 + (n-5*var1)//3)
            break
        else:
            var1 -= 1

        if var1 == -1:
            print(-1)
            break

 

- Greedy Algorithm

- Dynamic Programming

 

그리디로 풀었다.

기본 아이디어 : 5로 최대한 깎아보고 안되면 5씩 빼면서 3의 배수인지 탐색

 

dp로 푼다는 건 알았는데 잘 모루겟따ㄸ러ㄸ나ㅣㄻㅁㅇ....

인터넷 보고 좀 배움

import sys
input = sys.stdin.readline

n = int(input())

# dp 테이블 초기화
dp = [5001] * (n+5)

# dp 점화식
dp[3] = 1
dp[5] = 1

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

# dp 출력
print(dp[n] if dp[n] <= 5000 else -1)

이걸로 dp에 한걸음 다가갔길 빌며ㅠ