[백준 알고리즘][자바] 2839번 : 설탕 배달

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

2839번: 설탕 배달

안녕하세요. 이번 포스팅은 백준 알고리즘 2839번 : 설탕 배달입니다.

이번 문제는 그리디(Greedy) 알고리즘의 문제인거 같습니다.

설탕 N킬로그램을 3킬로그램 봉지와 5킬로그램 봉지을 이용하여 배달을 한다고 할때, 봉지의 최소 개수를 출력하는 문제입니다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력합니다.

 

봉지를 최소 개수로 사용하기 위해선 5킬로그램의 봉지의 개수를 기준으로 삼아야 합니다.

몇가지 예를 들어보자면

• N = 21 일때, 5킬로그램 봉지 3개, 3킬로그램 봉지 2개 = 총 5개
• N = 22 일때, 5킬로그램 봉지 2개, 3킬로그램 봉지 4개 = 총 6개
• N = 23 일때, 5킬로그램 봉지 4개, 3킬로그램 봉지 1개 = 총 5개

위의 예시처럼 N킬로그램을 5로 나눈 몫이 4인수들이 5킬로그램 봉지를 무조건 4개를 사용하는 것이 아닌

남은 킬로그램에 따라 5킬로그램 봉지의 사용개수가 달라지는 것을 확인할 수 있습니다.

 

5킬로그램 봉지와 3킬로그램 봉지를 조합하여 배달할 수 있는 킬로그램 수들을 살펴보면

• 5킬로그램 봉지 1개 사용 -> 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44....
• 5킬로그램 봉지 2개 사용 -> 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49...
• 5킬로그램 봉지 3개 사용 -> 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48...
• 5킬로그램 봉지 4개 사용 -> 23, 26, 29, 32, 35...
• 5킬로그램 봉지 5개 사용 -> 28, 31, 34, 37, 40...

킬로그램 수들을 보시게 되면 5킬로그램 봉지를 1개 사용할때와 4개 사용할때, 2개 사용할때와 5개 사용할때의  수들이 겹치는 것을 확인할 수 있습니다.

이것이 의미하는 것은 N킬로그램을 배달할때 5킬로그램 봉지와 3킬로그램 봉지를 조합하여 배달하는 경우의 수가
총 3가지라는 것을 의미합니다.

1.  N을 5로 나눈 몫
2.  N을 5로 나눈 몫 - 1
3.  N을 5로 나눈 몫 - 2

또한 3킬로그램 봉지만을 사용하여 배달하는 경우는 이미 5킬로그램 봉지 3개 사용시에 포함되어 있기 때문에

위의 3가지 경우의 수에 포함되지 않으면 정확하게 N킬로그램을 만들 수 없는 -1에 해당합니다.

아마 이 3가지의 경우의 수는 3과 5의 최소공배수와 연관되지 않을까 생각해봅니다.(정확하지는 않습니다.)

마지막으로 5킬로그램 봉지만을 이용하여 배달하는 경우의 수가 있습니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine()); // N킬로그램
		int anwser = 0; // 봉지의 갯수
		
		if(N % 5 == 0) { // 5킬로그램 봉지만을 이용
			anwser = N / 5; 
		}else {
			for(int i = 0; i < 3 ; i++) { // 몫, 몫-1, 몫-2의 경우의 수
				if(N / 5 - i < 0) { // 만약 몫이 음수이면 배달 불가능
					anwser = -1;
					break;
				}else if((N - 5 * (N / 5 - i)) % 3 == 0) { // 3가지의 경우의 수
					anwser = ((N / 5) - i) + (N - 5 * ((N / 5) - i)) / 3;
					break;
				}
				anwser = -1; // 위의 모든 경우의 수에 포함되지 않으면 -1
			}
		}
			
		bw.write(String.valueOf(anwser));

		br.close();
		bw.flush();
		bw.close();
	}
}