[코테 매일 풀기 13일차] 1121

백준 1654 랜선 자르기

아이디어

• 처음에 이분탐색인지 모르겠음.
• 의사코드

left = 1, right = max(랜선들) 
while(left <=right): 
	mid = (left+right) / 2
    if(mid로 잘랐을때 개수가 N이상이면): //길이를 늘려야함 
    	answer = mid; //저장 
        left = mid+1; 
    else: 
    	right= mid -1; 

package boj_silver.p1654_랜선자르기;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int ans;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt(); int n = scan.nextInt();
        //k개 입력 받기
        //랜선 길이가 최대 2^32 - 1이므로 long 사용
        long[] arr = new long[k];
        for (int i = 0; i < k; i++) {
            arr[i] = scan.nextLong();
        }
        long left = 1;
        long right = 0;
        //최댓값
        for (int i = 0; i < k; i++) {
            right = Math.max(right, arr[i]);
        }
        long ans = 0;

        while(left<=right){
            long mid = (left+right)/ 2;
            //돌면서
            long sum = 0;
            for (int i = 0; i< k; i++){
                sum += arr[i] / mid;
            }
            if(sum>=n){
                ans = mid;
                left = mid+1;
            }else{
                right = mid-1;
            }
        }//while
        System.out.println(ans);

    }
}