백준 2839 - 설탕 배달(자바 - 그리디)

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

2839번: 설탕 배달

 

* 문제 요약

사탕 가게에 설탕을 정확하게 N 킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다.

봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

최대한 적은 봉지를 들고 가려고 한다. 예를 들어 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면 더 적은 갯수의 봉지를 배달할 수 있다.

설탕을 정확하게 N 킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 N이 주어진다.(3 <= N <= 5000)

 

* 출력

배달하는 봉지의 최소 갯수를 출력한다. 만약 정확하게 N킬로그램을 만들 수 없다면 -1 을 출력한다.

 

* 예시 

 

* 해결 과정

백준 14916 - 거스름돈 문제와 거의 동일한 문제이다.

5킬로그램 봉지를 한 개도 사용하지 않는 경우부터 시작해서 5킬로그램 봉지만으로 n킬로그램을 넘기기전까지 3킬로그램 봉지와 조합해서 n킬로그램을 만들 수 있는 조합중 봉지를 최소로 사용하는 경우를 찾으면 되는 문제이다.

만약 어떠한 조합으로도 n킬로그램을 만들 수 없다면 -1 을 출력해주면 된다.

 

* 코드

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 {
		new Main().solution();
	}

	private void solution() 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());

		boolean check = false;

		int fiveCount = 0;
		int min = Integer.MAX_VALUE;
		while (5 * fiveCount <= n) {
			int spare = n - (5 * fiveCount);

			if (spare > 0) {
				int threeCount = spare / 3;
				int change = spare % 3;
				if (change > 0) {
					fiveCount++;
				} else if (change == 0) {
					min = Math.min(min, fiveCount + threeCount);
					fiveCount++;
					check = true;
				}
			} else if (spare == 0) {
				min = Math.min(min, fiveCount);
				fiveCount++;
				check = true;
			}
		}
		if (check) {
			bw.write(min + "\n");
		} else {
			bw.write(-1 + "\n");
		}
		bw.flush();
		bw.close();
	}
}

 

거스름돈 문제와 같이 사용되는 봉지의 갯수를 최소화 시켜야 하기 때문에 5킬로그램 짜리 봉지를 먼저 사용해보는 방식으로 각 단계마다 3킬로그램 짜리 봉지와의 조합으로 n킬로그램을 만들 수 있는 최적의 조합을 찾는 그리디 알고리즘 방식으로 문제를 풀었다.

 

또한 n킬로그램을 만들 수 있는 모든 조합을 찾는 작은 문제풀이, 그리고 작은 문제풀이의 결과를 저장해두고 활용하는 메모이제이션 기법을 통해 봉지를 최소로 사용하는 경우. 즉, 큰 문제를 풀었으므로 다이나믹 프로그래밍 기법 또한 활용되었다.