[백준] 2839번 문제 풀이

2839번. 설탕 배달

시간 제한 : 1초
메모리 제한 : 128MB
알고리즘 분류 : 수학, 다이나믹 프로그래밍, 그리디 알고리즘

문제 요약
설탕공장에서 일하는 상근이는 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에 봉지는 3킬로그램과 5킬로그램이 있다. 최대한 적은 봉지를 들고가려고 한다. 예를 들어, 18킬로그램 설탕을 배달하려면 5킬로그램 3개와 3킬로그램 1개를 배달할 수 있다. 상근이가 봉지를 몇 개 가져가면 되는지 작성해라.

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

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

예제 입력 1
18

예제 출력 1
4

예제 입력 2
4

예제 출력 2
-1

예제 입력 3
6

예제 출력 3
2

예제 입력 4
9

예제 출력 4
3

예제 입력 5
11

예제 출력 5
3

---

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = 0, five = 0, three = 0;
		num = sc.nextInt();
		
		int num_copy = num;
		while (true) {
			if (num_copy >= 5) {
				num_copy -= 5;
				five++;
			} else if (num_copy >= 3) {
				num_copy -= 3;
				three++;
			} else if (num_copy > 0) {
				num_copy += 5;
				five--;
				num_copy -= 3;
				three++;
				
				if (five < 0) {
					System.out.println(-1);
					break;
				}
			} else if (num_copy == 0) {
				System.out.println(five + three);
				break;
			} else {
				System.out.println(-1);
				break;
			}
		}
	}
}

---

메모

오랜만에 백준 문제를 들고 온 이유는 처음 문제를 봤을 때 되게 쉬운 문제인 줄 알았는데 생각보다 헤맸기 때문에 가져왔다. 예제 입출력은 잘 나오는데 정답처리가 안 되어서 반례도 찾아보고 했지만 계속 해결되지 않았는데 생각보다 가까운 곳에 문제가 숨겨져 있었다.

내 풀이 방법은 먼저 5씩 지우고 그 다음 3을 지우는 순서로 되어 있는데 이후 5와 3을 제외하고 3보다 작고 0보다 큰 수만 남았을 경우 다시 5를 더하고 3을 빼는 방법으로 주어지는 숫자가 5와 3으로 딱 나누어 떨어지는지를 확인하려고 했다.

 

그러나 7을 입력할 경우 five--를 하는 과정에서 five가 마이너스임에도 계속 조건이 돌아 결국 7의 결과 값이 -1이 아닌 3이 되어 버리는 경우가 생겨버렸다.

 

1) 7에서 5를 뺌 (num_copy : 2, five : 1, three : 0)

2) five를 1 빼고 three 1을 더함 (num_copy : 4, five : 0, three : 1)

3) 4에서 3을 뺌 (num_copy : 1, five : 0, three : 2)

4) five를 1 빼고 three 1을 더함 (num_copy : 3, five : -1, three : 3) < 여기서 문제가 됨

 

five가 마이너스 임에도 조건이 돌다보니까 num_copy가 0이 될 때까지 돌기 때문에 -1의 경우를 찾을 수 없는 구조가 되었다. 그래서 five가 마이너스일 경우의 조건을 추가하였다.

 

해결!