BOJ2839 설탕 배달

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

2839번: 설탕 배달

난이도: 실버4

풀이 시간: 40분.... 15분만에 풀었으나 엣지케이스를 발견을 하여.. 알고리즘을 새로 짬..

 

아래는 나의 코드이다. 3으로 빼주면서 5의 배수가 될때마다 리스트에 추가하여 최솟값을 마지막에 출력한다.

 

문제를 보자마자 DP가 떠올랐다. DP[i-3]과 DP[i-5]를 비교하면 되겠다는 생각이 바로 떠올라 점화식이 쉽게 생각났지만 오늘은 그리디를 공부하기로 한 날이기에 그리디로 풀었다.

import sys

N=int(sys.stdin.readline())

def count(N):
    i = 0
    temp=[1e9]
    while(N>=3):
        if N==3:
            temp.append(i+1)
        if N%5==0:
            temp.append(i+N//5)
        i+=1
        N = N - 3
    return min(temp)


result =count(N)
if result ==1e9:
    print(-1)
else:
    print(result)