[백준 2839] 설탕배달 - 수학, DP, 그리디

코드

def solution(n):
    cnt_5 = n//5
    
    while cnt_5 != 0:
        if (n - cnt_5*5)%3 == 0:
            break
        cnt_5 -= 1
    
    if cnt_5 != 0:
        return cnt_5 + (n - cnt_5*5)//3
    else:
        if n % 3 == 0:
            return n // 3
        else:
            return -1
        

n = int(input())
print(solution(n))

 

설명

• 최대한 제일 적은 개수의 봉지로 배달을 해야한다
• 그러므로 5킬로그램 봉지를 최대한 많이 사용하되, 나누어 떨어지게 3킬로 그램 봉지를 사용해야 한다
• 5킬로그램 봉지를 최대로 잡고, 하나씩 줄이면서 3으로 나누어 떨어지는지 확인한다
• 나누어 떨어진다면 5킬로그램 봉지 개수와 3킬로그램 봉지 개수를 더한값을 출력한다
• 5킬로그램 봉지가 0개 인데, 3으로 나누어 떨어지지 않으면 정확하게 n킬로그램을 만들 수 없으므로 -1을 출력한다