[백준 / 그르다 김가놈 / JAVA / 이분 탐색]

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

18113번: 그르다 김가놈

 

문제 접근

주어진 김밥 길이를 꼬다리를 정리 후 배열에 저장, 꼬다리 길이에 못미치는 김밥은 폐기

저장된 배열 김밥 길이들을 토대로 김밥 최소 갯수를 만들 수 있어야 하며 자르는 김밥의 길이도 최대로 해주고 싶다.

 

자르고자 하는 김밥의 길이가 길수록 만들 수 있는 김밥의 갯수는 줄어들 것이다.

mid 전체 길이를 반씩 자르면서 최적의 김밥 길이를 찾아야한다.

 

최소 김밥 갯수에 미치지 못한다면 현재 자르는 김밥 길이(mid)가 너무 길기 때문이니까 right를 감소

김밥 갯수를 충족한다면 더 큰 길이로 자를 수 있는지 확인하기 위해 left를 증가시키고 현재 길이를 저장

 

이 작업을 반복하면서 while문을 빠져나가기 전 저장된 mid의 값이 최적의 김밥 길이이다. 

 

단 한 순간도 김밥 갯수를 충족시키지 못한다면 만들 수 없는 상황이기에 -1 출력

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

public class Main {
	public static void main(String[] args) throws IOException {
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 StringTokenizer st = new StringTokenizer(br.readLine());
	 
	 int N = Integer.parseInt(st.nextToken()); // 김밥 갯수
	 int K = Integer.parseInt(st.nextToken()); // 꼬다리 길이
	 int M = Integer.parseInt(st.nextToken()); // 김밥 조각 최소 갯수
	 
	 int[] gimbap = new int[N];
	 
	 for(int i=0; i<N; i++) {
		 
		 int trimGimbap = Integer.parseInt(br.readLine());
		 
		 if(trimGimbap <= K) trimGimbap = 0;
		 else if(trimGimbap < K*2) trimGimbap = trimGimbap - K;
		 else trimGimbap = trimGimbap - K*2;
		 
		 gimbap[i] = trimGimbap;
	 }
	 
	 int left = 1;
	 int right = 1000000000;
	 int P = -1;
	 
	 while(left <= right) {
		 int mid = (left + right) / 2;
		 int count = 0;
		 for(int i=0; i<N; i++) count += (gimbap[i] / mid);
		 
		 if(count >= M) {
			 P = mid;
			 left = mid + 1;
		 }
		 else {
			 right = mid - 1;
		 }
	 }
	 System.out.println(P);
	}
}