[백준 2839번 ] 설탕 배달 (파이썬/python)

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

2839번: 설탕 배달

 

N이 5000밖에 안 돼서 dp말고 단순 무식 반복문으로도 충분히 풀 수 있을것 같았는데 그냥 dp로 풀었다.

메모이제이션 하며 5키로로 분할했을때, 3키로로 분할했을떄 두 경우중 최소값을 출력하며 메모이제이션 dp를 갱신해줬다.

 

 

import sys
sys.setrecursionlimit((10000))
 
input = sys.stdin.readline
dp = [987654321] * 5001
n = int(input())
 
 
def devide(x):
    if x == 1 or x == 2:
        return 987654321
    # 정확히 나뉘었으면 횟수 반환
    if x == 0:
        return 0
    if dp[x] != 987654321:
        return dp[x]
 
    # 5보다 크면 5랑 3으로 나눈것중 가장 작은값을 출력
    if x >= 5:
        dp[x] = min(devide(x - 5) + 1, devide(x - 3) + 1)
    else:
        dp[x] = devide(x - 3) + 1
 
    return dp[x]
 
 
cnt = devide(n)
if cnt >= 987654321:
    print(-1)
else:
    print(cnt)