[백준 1654] 랜선 자르기_자바Java

1. 문제

https://www.acmicpc.net/problem/1654
K개의 랜선이 있고, 똑같은 길이의 N개의 랜선을 만들고자 할 때, N개의 랜선이 가질 수 있는 최대 길이를 알아내는 문제

2. 풀이

| Parametric Search

이분탐색과는 다르게 여기서는 조금 관점을 바꿀 필요가 있다.
이 문제에서 이분 탐색의 범위는 인덱스가 아닌 랜선의 '길이'이기 때문이다.

고려해야 할 점은 Upper bound와 Lower bound이다.
상한값을 찾고자 하는 경우엔 특정 값을 초과하는 '첫 위치'를 반환하고,
하한값을 찾고자 하는 경우엔 특정 값 이상인 '첫 위치'를 반환한다.

본 문제에서 주어진 예제로 설명하자면,
11개가 넘는 경우는 198cm, 199cm, 200cm 모두 가능하다. 하지만 랜선의 '최대길이'라는 조건을 찾기 위해서는 Upper bound를 통해 얻어진 값으로 최대 길이를 찾을 수 있다.

3. 코드

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

public class BOJ1654 {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int K = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int lines[] = new int[K];
	
		// 랜선 정보 입력받기
		for(int i = 0; i < K; i++) {
			lines[i] = Integer.parseInt(in.readLine());
		}
		Arrays.sort(lines);
		
		long left = 1, right = lines[K-1];
		while(left <= right) {		
			long mid = (left + right) / 2;
			long sum = 0;
			
			// 총 몇개의 랜선이 만들어지는지 구하기
			for(int i = 0; i < K; i++) {
				sum += lines[i]/mid; 
			}
			
			if(N <= sum) left = mid + 1;
			else right = mid - 1;
		}
		
		System.out.println(right);
		in.close();

	}
}