[백준] 1654 랜선자르기

문제보기

이분탐색 재밌당…! 그냥 랜선 쭉 받은다음에 정렬하고, 큰 길이부터 쭉쭉 탐색하면서 내가 정한 기준 길이를 몇개나 만들어낼 수 있는지 합산해주면 된다.
자세한 내용은 주석으로~!

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

class Main{
	
	static int ip(String s){ return Integer.parseInt(s); };
	
     public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int k = ip(st.nextToken());
    	int n = ip(st.nextToken());

    	int[] lans = new int[k]; // 랜선 길이를 입력받자 
    	for(int i = 0 ; i < k ; i++) {
    		lans[i] = ip(br.readLine());
    	}
    	Arrays.sort(lans); // 오름차순으로 정렬(뭐든 딱히 상관없음)
    	long l = 1; // 최소 길이 
    	long r = lans[k-1]; // 최대 길이(이 값이 최대가 나오면 터지기 때문에 ㅠㅠ long으로 입력받자.
    	long ans = 0; // 정답길이가 저장될 변수 
    	
    	while(l <= r) { // 이분탐색 ㄱㄱ
    		long mid = (l+r)/2; // 중간값을 기준으로 
    		int cnts = 0; // mid길이를 만들어낼 수 있는 최대 랜선갯수를 저장 
    		
    		for(int i = k-1 ; i >=0 ; i--) { // 큰 길이들 부터 조사 
    			int cnt = (int)(lans[i]/mid); // 이 길이 몇개나 만들어주실 수 있으세요? 
    			if(cnt < 1) break; // 한개도 못만드신다구여? 나갈게요..
    			cnts += cnt; // 저장 
    		}
    		
    		if(cnts >= n) { // n개보다 더 만들었다면 
    			l = mid + 1; // 길이를 늘려보자 
    			ans = mid; // 저장
    			
    		}else { // n개보다 모자르다면 
    			r = mid - 1; // 길이를 줄여보자
    		}
    	}

    	System.out.println(ans);
     }
}