알고리즘
[백준 2839] 설탕배달 - 수학, DP, 그리디
kyeongjun-dev
2021. 12. 29. 11:22
코드
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을 출력한다