[백준 알고리즘 - 2839] 설탕 배달

문제 : 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

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

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

입력 조건 : 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

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

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

문제가 조금은 어려워졌기 때문에 먼저 소스코드부터 보고 추가 설명 진행하겠습니다.

(못쓰는 글을 뽐내자)

package Algorithm;

/* 문제 : 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 
 * 설탕을 정확하게 N킬로그램을 배달해야 한다. 
 * 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
 * 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 
 * 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 
 * 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
 * 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때,
 * 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. */

public class Algorithm2839 {

	private final static int FIVE = 5;
	private final static int THREE = 3;
	private int F=0,  T=0;
	
	// 나눈 값이 딱 떨어져야지 상근이는 설탕을 배달할 수 있다.
	public void print(int A){
		if(3 <= A && A <= 5000){
			F = A / FIVE;										
			A = A % FIVE;
			while(F >= 0){
				if(A%THREE == 0){
					T = A / THREE;
					A = A % THREE;
					break;
				}
				F -= 1;
				A += FIVE;
			}
			if(A == 0 ) {System.out.println(F+T);}
			else System.out.println(-1);
		}
	}
}

먼저 문제의 의도를 확실히 해야합니다.

1. 상근이는 N 킬로그램을 배달할 때 봉지 몇개를 가져갈 수 있을까?

2. 상근이는 N 킬로그램을 정확히 맞춰서 배달해야한다.

위와 같이 2가지로 문제를 축소시킬 수 있습니다.

먼저 1번째는 결과값이기 때문에 해당 부분을 제외하고 2번째부터 정리해보겠습니다.

상근이는 N킬로그램을 5 or 3으로 나눠서 가져가야합니다.

가장 쉽게 접근하는 방법은 역시 큰 값으로 나눈 후 짝맞추기 식으로 진행하면 됩니다.

아래에 순서대로 설명을 작성하겠습니다.

1. F라는 변수에 N / 5 를 진행하여 5킬로그램을 몇개를 가져갈지 처음 정의를 내립니다.

2. N의 나머지 값을 구하여 N의 값을 변경합니다.

3. F의 값이 0보다 크거나 같을 동안 반복문을 진행합니다.

* 5킬로그램을 가져가는 갯수를 반복문을 진행하는 것인데, 5킬로그램을 0개 (즉, 안가져간다)가 될수 있기 때문에 0보다 크거나 같은 조건으로 반복문을 진행합니다.

4. 반복문 내부에서 N의 값을 3으로 나눈 나머지 값이 0이 된다면 상근이는 더이상 고민하지 않고 최소 개수를 구할 수 있습니다.

* 3으로 나누어 떨어진다면 T라는 값에 해당 몫을 넣어준 후 N의 값을 나머지값으로 변경해준다.(여기는 0) break문으로 조건문을 빠져나와 변수끼리 출력한다.

5. 만약 나누어 떨어지지 않는다면, 5킬로그램 봉지 1개를 빼고, 그 값을 N에 더한 후 루프를 진행한다.

6. 마지막으로 N == 0 이 아니면 상근이는 배달을 할 수 없으므로 -1을 출력한다.

두서없이 작성한것 같아 부족해보이지만 혹시라도 모르는 부분이 있으시면 답변드리겠습니다!

이상 많은 정보를 공유하고싶은 '코승이' 였습니다.

오늘도 좋은 하루보내시고 좋은 마무리를 기원합니다.

(공감은 많은 도움이 됩니다)