[백준] 16401번 과자 나눠주기 (JAVA)

문제

- 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 함

- 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 함

- M명의 조카가 있고 N개의 과작 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이 구하기

- 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없음

 

해결방법

처음에 문제를 꼼꼼히 읽지 않아서 틀렸습니다가 계속 떴었다... 과자의 길이가 속하는 범위만 주어졌었는데 왜 그렇게 문제를 읽었는지는 모르겠지만 L1~LN까지 크기 순서대로 정렬되어 주어진다고 생각하고 문제를 풀었다. 나중에 다시 보니 해당 부분이 문제였고 정렬하는 코드를 추가해주어서 이를 해결하였다.

전체적인 문제는 이분 탐색으로 해결하였고, 막대 과자의 길이를 이분 탐색으로 구해나아가면서 해당 길이일 때, 조카들에게 모두 과자를 줄 수 있는지를 판단하면서 길이를 최대로 늘려나가면서 구했다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());		// 조카의 수
        int N = Integer.parseInt(st.nextToken());		// 과자의 수
        int[] snack = new int[N];
        long result = 0;					// 막대 과자의 최대 길이

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            snack[i] = Integer.parseInt(st.nextToken());
        }
		
        // 문제의 정렬 코드...
        Arrays.sort(snack);
		
        // 막대 과자의 최대 길이를 구하기 위한 이분 탐색
        long left = 1;
        long right = snack[N-1];

        while (left <= right) {
            int count = 0;
            long mid = (right + left) / 2;
			
            // 막대 과자 길이를 특정한 뒤 몇명의 조카에게 줄 수 있는지 계산
            for(int i = 0; i<N; i++) count += snack[i] / mid;
			
            // 조카의 수보다 막대 과자가 많이 나오면 해당 길이만큼 나누어줄 수 있음
            // 계속 반복하면서 범위를 좁혀나가고, 막대 과자의 길이를 최대로 특정함
            if(count >= M) {
                if(result < mid) result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
		
        // 막대 과자의 최대 길이 출력
        System.out.println(result);
    }
}