백준 16401 과자 나눠주기 자바로 풀어 본 짧은 글

백준 16401 과자 나눠주기

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

16401번: 과자 나눠주기

접근 방식

길이를 기준으로 이분탐색, 과자의 개수에 따라서 m명의 조카에게 나눠줄 수 있는지 판단하는 것이 중요!

---

구현 방법

• 이분탐색을 위한 범위
• 과자를 활용할 배열

⇒

배열로 과자를 입력받은 후 받은 과자 배열의 요소를 모두 탐색 → 이분탐색의 중앙값을 기준으로 해당 과자의 갯수를 카운트하고, 카운트의 갯수와 입력받은 m의 수가 일치한다면 과자를 동일한 길이로 줄 수 있는 것이기 때문에 해당 값을 정답에 저장 → 길이가 포함된다면 이분탐색 피벗기준 우측, 포함되지않으면 피벗기준 좌측

---

풀이

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

public class p16401_2 {
    public static void main(String[] args) throws IOException{
        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[] a = new int[n];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(a);
        int maxCookieLength = 0;
        int left = 1;
        int right = a[n-1];
        while(left <= right){
            int count = 0;
            int center = (left + right) / 2;
            //m을 기준으로 몇개가 나오는지 카운트
            for(int i = 0; i <n; i++){
                count += a[i]/center;
            }

            if(count >= m){
                maxCookieLength = center;
                left = center+1;
            }else{
                right = center-1;
            }
        }

        System.out.println(maxCookieLength);

    }
}

---

후기

이분탐색임을 알고 시작했는데, 아직 익숙하지 않아서 접근이 어려웠다.