[백준] 설탕 배달 (그리디 Greedy 알고리즘 , 2839번, Java)

 

문제설명

입력 & 출력

 

나의 풀이

 

 

이번 문제는 봉지는 3kg, 5kg가 있으며 최대한 적은 봉지를 사용하면서 Nkg의 설탕을 정확하게 배달하는 문제입니다. 

 

그리디 알고리즘의 문제로서 가장 적은 봉지를 사용하려면 kg가 큰 5kg 봉지를 최대한 많이 사용해야 하는 것은 당연합니다.

 

먼저 while문을 사용하여 반복문을 돌려줍니다. 이때 5로 나누어 떨어지는 경우 5로 나눈 몫을 봉지 개수 cnt에 누적을 합니다.

 

만약 5kg봉지로만 정확하게 배달할 수 있으면 최적의 경우이기 때문에 그대로 return 해줍니다.

• 예를 들어 설탕이 15kg라면
• 5kg봉지 3개만 필요합니다.

그러나 5kg봉지로만 배달할 수 없다면 3kg 봉지를 어쩔 수 없이 사용해야 하기 때문에 설탕을 3만큼 빼주고 봉지 개수 cnt를 추가합니다.

 

• 예를 들어 설탕이 18kg라면
• 5kg 봉지 3개 + 3kg 봉지 1개 == 4개

또한 5kg와 3kg봉지를 사용하고도 정확히 배달할 수 없는 경우 (4kg, 7kg, 11kg) 

 

• 설탕이 4kg라면
• 3kg 봉지 1개, 남은 설탕 1kg ➡️ 5로 나누어 떨어지지 않기에 else문을 탑니다.
• 1kg 남음 : 1 - 3 = -2
• sugar이 음수이기 때문에 while문을 빠져나와 -1을 출력합니다.

• 설탕이 7kg라면
• 5kg 봉지 1개, 남은 설탕 2kg ➡️ 5로 나누어 떨어지지 않기에 else문을 탑니다.
• 2kg 남음 : 2 - 3 = -1
• sugar이 음수이기 때문에 while문을 빠져나와 -1을 출력합니다.

• 설탕이 11kg라면
• 5kg 봉지 2개, 남은 설탕 1kg ➡️ 5로 나누어 떨어지지 않기에 else문을 탑니다.
• 1kg 남음 : 1 - 3 = -2
• sugar이 음수이기 때문에 while문을 빠져나와 -1을 출력합니다.

 

참고❗️

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기