[백준 : 브론즈1] 설탕배달 : DP(Java)

이번 문제는 약간의 힌트만을 보고 내가 직접 소스를 짜서 문제를 풀어냈다.

 

일단 문제부터 보자.

 

문제

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

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

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

입력

첫째 줄에 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

 

 

이번 문제의 가장 핵심은 최대한 적은 가방으로 설탕을 담는것이다.

따라서 이 조건을 맞추려면 일단 5g을 담는 가방의 수부터 구해야 한다.

 

그래서 내가 제일먼저 한것은 설탕을 5로 나눴을떄 나누어 떨어지는지 안나누어 떨어지는지를 구했다.

 

그래서 가장 겉에 감싸져 있는 if문은 아래와 같다.

 

		int answer = 0;
		int devF = n/5; //5로 나눈 몫
		int rest = n%5;//5로 나눈 나머지
		int devT = 0; //3으로 나눈 몫
		
		if(rest == 0) { //5로 나눠 떨어졌을때 진입
			answer = devF; //5로 나눈 몫 return
		}else {//5로 나눠떨어지지 않을때 진입

		}
        
        return answer = devF+devT;

 

그럼 이제 5로 나누어 떨어지면 5로 나눈 몫을 return 하게 했다.

그럼 이제 그 다음으로 해야 할것은 5로 나누어 떨어지지 않을때를 구하는것이다.

 

---

 

5로 나누었을때 나올수 있는 나머지는 아래와 같다.

1,2,3,4

그중 3으로 나누었을때 나누어 떨어지는경우라면 그냥 나머지를 3으로 나눈 몫을 구하면 된다.

그래서 나는 조건문을 아래와 같이 만들었다.

 

		int answer = 0;
		int devF = n/5; //5로 나눈 몫
		int rest = n%5;//5로 나눈 나머지
		int devT = 0; //3으로 나눈 몫
		
		if(rest == 0) { //5로 나눠 떨어졌을때 진입
			answer = devF; //5로 나눈 몫 return
		}else {//5로 나눠떨어지지 않을때 진입
			if(rest%3 != 0) { //5로 나눈 나머지를 3으로 나눴을때 맞아 떨어지지 않는다면 진입

			}else { //5로 나눈 나머지를 3으로 나눴을때 맞아 떨어지는 경우
				devT = rest/3;
			}			
		}
		return answer = devF+devT;

 

그럼 이제 5로 나눈 나머지가 3으로 나누어 떨어지지 않았을때를 구해야 한다.

 

그럴때는 우리가 해줘야 할것은 5g 봉지를 하나빼고 남는 설탕이 3g봉지로 나누어 떨어지는 지 봐야 한다.

이게 무슨소리냐면

6g이 있다면 

11 / 5 = 1 이 되어서 5g  *  2를 만들수 있다.

 

하지만 설탕을 다 담지 못하니 5g 한봉지를 빼고 남는 설탕수를 구한다.

 

위의 예를 통해서 구하자면 남는 설탕은 6g이 된다.

11 - (5*1) = 6

 

6g으론 3g 봉지 두개가 나오게 되니 

11g은 총 

5g봉지 하나 3g 봉지 2개가 나오게 된다.

 

이처럼 우리가 해야할것은 5g의 봉지를 한개도 남지 않을때까지 봉지를 한개씩 줄여서

남는 설탕이 3g으로 나누어 떨어지는지 확인해야 한다.

해당 부분이 아래와 같다.

 

		while(devF > 0) { //devF가 0이 될때까지 반복, 이미 0이면 들어가지 않음
			devF -=1;
			int temp = 5*devF;
			int mTemp = n-temp;
			if(mTemp%3  == 0) { //5봉 하나빼고 남은 수를 3으로 나눴을때 나눠 떨어지면 진입
				devT = mTemp/3; //남은 수를 3으로 나눈 몫을 구하고
				break;
			}
		}

그럼 이제 해당 부분을 나오게 되면 5g봉지 개수와 3g봉지 개수가 나오게 된다.

 

이때 둘다 하나도 나오지 않게 되는것은 나누어 떨어지지 않는것이므로 -1을 리턴하면 된다.

 

그래서 총 소스는 아래와 같다.

import java.util.Scanner;

public class Run {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Run a = new Run();
		Scanner sc = new Scanner(System.in);
		int sugar = sc.nextInt();
		System.out.println(a.minBag(sugar));
	}
	
	public int minBag(int n) {
		int answer = 0;
		int devF = n/5; //5로 나눈 몫
		int rest = n%5;//5로 나눈 나머지
		int devT = 0; //3으로 나눈 몫
		
		if(rest == 0) { //5로 나눠 떨어졌을때 진입
			answer = devF; //5로 나눈 몫 return
		}else {//5로 나눠떨어지지 않을때 진입
			if(rest%3 != 0) { //5로 나눈 나머지를 3으로 나눴을때 맞아 떨어지지 않는다면 진입
				while(devF > 0) { //devF가 0이 될때까지 반복, 이미 0이면 들어가지 않음
					devF -=1;
					int temp = 5*devF;
					int mTemp = n-temp;
					if(mTemp%3  == 0) { //5봉 하나빼고 남은 수를 3으로 나눴을때 나눠 떨어지면 진입
						devT = mTemp/3; //남은 수를 3으로 나눈 몫을 구하고
						break;
					}
				}
				if(devF == 0 && devT == 0) { //5봉으로도 못나누고 3봉으로도 못나누면 -1
					return -1;
				}
			}else { //5로 나눈 나머지를 3으로 나눴을때 맞아 떨어지는 경우
				devT = rest/3;
			}			
		}
		return answer = devF+devT;
	}
}

 

내소스는 좀 길게 나왔는데 다른 사람들의 소스는 엄청 짧게 나왔다.

그이유가 나는 반복문을 사용해서 나누어 떨어지는지 확인해봤지만 다른 사람들은 

조건문을 통해서 모든것을 걸러냈다.

 

하지만 알고리즘은 비슷한 방식으로 흘러가기에 따로 소스 분석을 하지 않고 해당 링크만 올려둘 예정이다.

https://st-lab.tistory.com/72

[백준] 2839번 : 설탕 배달 - JAVA [자바]

 

느낀점

 

1. 테스트케이스를 일일히 적용해보자