[반례모음] 백준 2839번: 설탕 배달 python 파이썬

1. 문제

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

2839번: 설탕 배달

 

 

2. 풀이

DP

 

 

3. 구현

import sys
# sys.stdin = open('input.txt')
import math

target = int(sys.stdin.readline().strip())
lis = [math.inf]*5002
lis[3] = 1
lis[5] = 1

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

if lis[target]==math.inf:
    print(-1)
else:
    print(lis[target])

 

 

4. 반례모음

 

@dbshin59 

4999

답: 1001

 

@ zigui

5000

답: 1000

 

 

@ pinoco3

3

답: 1

 

5

답: 1