[백준] 1654번. 랜선 자르기 (JAVA)

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

---

문제

 

---

풀이

 

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner kb = new Scanner(System.in);
		
		int k = kb.nextInt();
		int n = kb.nextInt();
		
		int[] arr = new int[k];
        for(int i=0; i<k; i++) {
            arr[i] = kb.nextInt();
        }
        
        Arrays.sort(arr);
        
        long max = arr[k-1]; 
        long min = 1; 
        long mid = 0;  
        
        while(max >= min) {
        	long sum = 0;
            mid = (max+min)/2;

            for(int j=0; j < k; j++) {             
                sum += arr[j]/mid;
            }
            
            if(sum >= n) {                
                min = mid + 1;               
            }else if(sum < n) {               
                max = mid - 1; 
            }
            
        }
        
        System.out.println(max);
        
    }
 
}

시작 기준 점을 어떻게 잡는지가 제일 중요한 문제이다. 랜선의 길이는 1부터 제일 긴 랜선의 길이까지 모두 가능하기에 둘의 평균으로 정한다. 이 후 길이 비교를 통해 시작점 혹은 끝점을 하나씩 조절해가며 길이를 찾아가면 된다.