[JAVA] 백준 과자 나눠주기

ex) 3명의 조카에게 1개의 과자 3cm인 경우=> 3등분 해야함.

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

 

이분탐색 문제였다.

처음에는 Priority Queue로 각각의 경우를 나눠주는 방식으로 접근했지만, 아래 예시와 같은 경우를 따지려니 실패하였다.

 

ex) 3명의 조카에게 1개의 과자 3cm인 경우=> 3등분 해야함.

 

따라서 위 방식은 잘못되었음을 깨닫고 이분탐색 방식으로 진행해야했다.

 

 

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

public class Main {
​​​​static int[] arr;
​​​​static int m, n,result;

​​​​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());
​​​​​​​​arr = new int[n];
​​​​​​​​st = new StringTokenizer(br.readLine());

​​​​​​​​for (int i = 0; i < n; i++) {
​​​​​​​​​​​​arr[i] = Integer.parseInt(st.nextToken());
​​​​​​​​}
​​​​​​​​Arrays.sort(arr);
​​​​​​​​binarySearch(1, arr[n-1]);

​​​​​​​​System.out.println(result);
​​​​}

​​​​public static void binarySearch(int start, int end) {
​​​​​​​​if(start>end) return;
​​​​​​​​int mid = (start+end)/2;
​​​​​​​​int cnt= 0;
​​​​​​​​for (int i = 0; i < n; i++) cnt+= arr[i]/mid;

​​​​​​​​if(cnt >= m) {//오른쪽
​​​​​​​​​​​​if(result < mid) result=mid;
​​​​​​​​​​​​binarySearch(mid+1, end);
​​​​​​​​}else{//왼쪽
​​​​​​​​​​​​binarySearch(start, mid-1);//왼쪽
​​​​​​​​}

​​​​}
}

테스트케이스 예시

3 10
1 2 3 4 5 6 7 8 9 10

 

첫번째시행->	우측->	우측->	좌측(start>end이므로 종료)
start = 1 end = 10 mid: 5 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 1 cnt = 2 cnt = 3 cnt = 4 cnt = 5 cnt = 7	start = 6 end = 10 mid: 8 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 1 cnt = 2 cnt = 3	start = 9 end = 10 mid: 9 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 0 cnt = 1 cnt = 2	start = 9 end = 8

----------------
result : 8