백준 2839 : 설탕 배달(그리디)

www.acmicpc.net/problem/2839

2839번: 설탕 배달

설탕 N(kg) 배달, 봉지는 3kg짜리와, 5kg 짜리가 있음

최대한 봉지를 적게 가져가는 것은? 

단, 정확하게 Nkg을 배달할 수 없으면, -1을 출력

거스름돈 문제와 비슷해 보이지만, 모든 경우의 수를 다 해봐야한다는 차이가 있음.

 

풀이:

5kg짜리 봉지를 많이 사용하는 순으로 --> 남는 양이 3의 배수인 지 체크하면서 갯수를 저장

ex. N=18 --> 5kg짜리를  3,2,1,0 순으로 사용하고--> 그때 남는 양이 3kg 봉지에 들어갈 수 있는지를 체크

 

def solve(N):
    n = N//5
    for i in range(n+1):
        temp = N-(n-i)*5
        if temp%3==0: return (n-i+temp//3)
    return -1

if __name__=='__main__':
    N = int(input())
    print(solve(N))