백준 2839 [설탕 배달] - JAVA

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

2839번: 설탕 배달

 

풀이

1. 5킬로그램의 봉지를 최대한 많이 선택해야한다.

  (3 ≤ N ≤ 5000) N의 범위가 3이상이기때문에 0개부터 계산한다.

2. 5킬로그램의 봉지 개수를 정할때 순차적으로 개수를 늘려나간다.

3. 5킬로그램의 봉지 개수를 먼저 선택한 후 3킬로그램의 봉지에 대해 고민한다.

  - 5킬로그램의 봉지 개수를 선택한 나머지가 3으로 나누어지지 않는다면 1번을 반복한다.

 

    만약 5킬로그램의 봉지개수가 0이고 3으로 나누어진다면 그것은 정답이라고 할 수 있을까? / 정답이 아닐 수 있다.

    21킬로그램의 최소 봉지 개수를 구한다고 생각해보자.

   

5킬로그램	3킬로그램	나머지	수식	개수
0	7	0	5x0 + 3x7 + 0	7
1	5	1	5x1 + 3x5 + 1
2	3	2	5x2 + 3x3 + 2
3	2	0	5x3 + 3x2 + 0	5

5킬로그램 봉지의 개수가 0개일때와 3개일때 둘다 정답의 조건은 만족한다.

하지만 우리는 최소 개수를 찾아야한다.

 

 

---

소스코드

package algorithm.greedy;

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

/**
 * 설탕 배당
 *
 */
public class Q2839 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int arr[] = {3,5};
		int nCnt = -1;
		int n5Bag = 0;
		int nMinCnt = Integer.MAX_VALUE;
		while(true) {
			//선택
			int n5BagWeight = 5 * n5Bag;
			
			//적절성 검사 & 해답 검사
			if(n5BagWeight > N) {
				break;
			}else if(n5BagWeight == N) {
				nCnt = n5Bag;
				break;
			}else {
				int nTempN = N - n5BagWeight;
				
				if(nTempN % 3 == 0) {
					nCnt = n5Bag + (nTempN / 3);
					
					if(nMinCnt > nCnt) {
						nMinCnt = nCnt;
					}
				}
			}
			n5Bag++;
		}
		
		System.out.println(nCnt);
	}

}