[BOJ 1654] 랜선 자르기 (Java)

BOJ 1654 랜선 자르기

문제풀이

기본적인 이분탐색 문제로 N개의 랜선들을 같은 길이의 랜선으로 자르는데, K개를 넘는 최대 개수가 되는 길이를 구하는 것이다.
1. 주어진 랜선을 길이 기준 오름차순으로 정렬한다.
2. 최소 1, 최대 주어진 랜선 중 가장 긴 길이를 시작으로 이분 탐색을 실시한다.
3. K개 이상으로 자르는 길이 중 최댓값을 구한다.

구현코드

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

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] wire = new int[N];
		
		for(int i = 0 ; i < N ; ++i) {
			wire[i] = sc.nextInt();
		}
		
		Arrays.sort(wire);
		
		System.out.println(binerySearch(K, wire));
	}

	private static long binerySearch(int k, int[] wire) {
		long left = 1;
		long right = wire[wire.length - 1];
		long mid = 0;
		long cnt = 0;
		long ans = 0;
		
		while(left <= right) {
			mid = (left + right) / 2;
			cnt = cutWire(mid, wire);
			
            // K 개 이상일 때 
			if(cnt >= k) {
            	// K개 이상을 만드는 길이중 최댓값을 구한다. 
				ans = mid > ans ? mid : ans;
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		
		return ans;
	}

	private static int cutWire(long length, int[] wire) {
		int cnt = 0;
		
		for(int w : wire) {
			cnt += w / length;
		}
		
		return cnt;
	}
	
}