백준 - 2839번(그리디)

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

2839번: 설탕 배달

 

import sys

n = int(sys.stdin.readline())
check = 0

x = n // 5 #5로만 담을 수 있는 최대 개수
y = n // 3 #3으로만 담을 수 있는 최대 개수

for i in range(x+1):
    for j in range(n):
        if 5*(x-i) + 3*j == n:
            print(x-i+j)
            check = 1
            exit(0)
            
if check == 0:
    print(-1)

최적해는 5를 최대한 많이 담는 경우다. 따라서 5kg짜리로만 담을 수 있는 최대 개수에서 한 개씩 감소하면서 3kg으로 담을 수 있는 모든 경우를 찾아볼 때 조건에 만족하면 출력하고 프로그램을 종료한다. 조건에 맞지 않는 경우 -1을 출력한다.