[백준 - 1654] 랜선 자르기 .java

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

 

• K개의 랜선을 잘라서 길이가 모두 같은 랜선 N개 이상 만들 수 있는 최대 길이 찾기
• 현재 길이로 잘라서 N개 이상 만들 수 있는지 판단

처음 이분 탐색으로 풀어야지 생각했지만 하나가 걸렸다

바로 현재 설정한 랜선 길이보다 더 짧은 랜선이 있을 경우 어떻게 되는가?였다

-> 답은 만들 수 없기에 0으로 누적된다

=> 더 짧은 랜선은 고려할 필요 없다

 

 

따라서 r의 최댓값은 입력 받을 수 있는 크기인 가장 긴 랜선 길이 ->  2^31-1보다 작거나 같은 자연수

int로  받으면 안되고 long 타입이여야함

 

1<<23

1 << n 

->  1을 왼쪽으로 n비트 밀기

->  결과적으로 2ⁿ

but, 2³¹ → int 범위 초과 오버플로우 발생 (주의!)

 

나눗셈이 포함된 이진 탐색 

=> mid가 0이 될 수 있는지를 항상 확인

=> l이 1부터 시작

 

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


public class Solution {
	//현재 cut 길이로 랜선을 자를 때 n개 이상 만들 수 있는지 확인하는 함수
	public static boolean isPossible(int[] len, long cut, int n) {
		long count = 0;
		for(int h : len) {
			if(h>=cut) count += h/cut;

		}
		return count >=n;//목표 개수 이상이면 true
	}

    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	
    	int k = sc.nextInt();
    	int n = sc.nextInt();
    	int[] lens = new int[k];
    	for(int i =0; i<k; i++) {
    		lens[i] = sc.nextInt();
    	}
    	Arrays.sort(lens);
    	//l: 자를 수 있는 최소 길이 (0은 나눗셈 오류 생기므로 1부터)
    	long l = 1, r = (1<<31) -1,answer = 0;
    	
    	while(l<=r) {

    		long mid = (l+r)/2;
    		//mid 길이로 잘랐을 때 n개 이상 만들 수 있다면 → 더 길게 자를 수 있는지 확인
    		if(isPossible(lens,mid,n)) {
    			answer = mid;//가능하니까 저장
    			l = mid+1;//그중 최댓값 찾아야함
    		} else r = mid-1;//더 짧게해야
    	}
    	
   		System.out.print(answer);
    	
    
     }
    
}