[백준] 16401 과자 나눠주기 - Java

 

 

 

문제 출저

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

16401번: 과자 나눠주기

 

 

 

문제 풀이

과자를 나눠줄 조카의 수 m, 과자의 수 n이 주어지고 n개의 과자 길이가 주어집니다.

과자의 길이를 설정해 조카들이게 나눠주는데 이 때 가장 긴 과장의 길이를 구하는게 이 문제의 요구사항입니다.

(조카에게 모두 동일한 크기의 과자를 주어야합니다. 그러지 못할 때는 0 출력)

 

 

이분 탐색으로 문제를 풀었습니다.

과자의 길이를 대상으로 탐색을 진행합니다. 

과자의 최소값은 1, 최대값은 1,000,000,000 입니다. 범위가 크므로 long으로 설정했습니다.

이분 탐색을 진행합니다. 이 때 과자의 설정값으로 과자의 값을 나누어 몇 개의 과자 조각이 나오는지 구했습니다.

이 과자 조각이 조카 수 m 이상이면 조건을 만족하는 것이므로 s = mid + 1을 하여 탐색 범위를 올렸고 그러지 못하는 경우 e = mid -1 을 하여 범위를 줄였습니다.

answer 변수를 생성하였고 0으로 초기화 했습니다. 조건이 충족했을 때만 answer = mid를 하여 조건을 충족 못했을 때 정답이 0이 나오도록 했습니다. 

 

 

 

소스 코드

package baekjoon.backjoon10.day0110.day02;


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

/*
과자 나눠주기
https://www.acmicpc.net/problem/16401
 */
public class B16401 {

    static int m, n;
    static long[] board;
    static long answer;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        board = new long[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            board[i] = Long.parseLong(st.nextToken());
        }

        long s = 1;
        long e = 1_000_000_000;
        answer = 0;

        while(s <= e) {
            long mid = (s+e)/2;

            int result = 0;
            for(int i = 0; i < n; i++) {
                result += board[i] / mid;
            }

            // 조건 충족
            if (result >= m) {
                s = mid+1;
                answer = mid;
            }
            else {
                e = mid-1;
            }
        }

        System.out.println(answer);


    }

}