백준 1654번: 랜선 자르기 [이분탐색][매개변수탐색]-Java

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

1654번: 랜선 자르기

 

 

<순서>

1. 배열 정렬

2. 자를 단위 X 구하기 (2^31-1 크기이기 때문에 long 처리)

3. X cm로 랜선 몇개 만들 수 있는지 계산

4. N개와의 비교 후 범위 조정하기

4-1. 현재가 N과 갯수가 같더라도 break하지말고 계속 확인해야함. 같더라도 X 길이가 더 큰 경우가 있을것이니..

4-2. N보다 클경우 랜선수가 너무 많으니 X 범위를 키운다. (더 크게 잘라보자)

 

<Java 코드>

package algorithm.boj;

import java.io.BufferedReader;
import java.io.FileInputStream;
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 {
		// TODO Auto-generated method stub

		System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int K = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		long arr[] = new long[K];
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Long.parseLong(st.nextToken());
		}
		
		//1. 배열 정렬
		Arrays.sort(arr);
		
		//자를 단위 X
		long x = Long.MIN_VALUE;
		//최초 조사범위는 (1 ~ 가지고있는 가장 큰 랜선길이) 로 지정
		long start = 1;
		long end = arr[K-1];
		
		while(start <= end) {
			//2. 자를 단위 X 구하기 (2^31-1 크기이기 때문에 long 처리)
			long mid = (start+end)/2;
			//3. X cm로 랜선 몇개 만들 수 있는지 계산
			int sum = 0;
			for (int i = 0; i < arr.length; i++) {
				sum += arr[i]/mid;
			}
			//4. N개와의 비교 후 범위 조정하기
			if (sum == N) { //같더라도 break하지말고 계속 확인해야함. 같더라도 X 길이가 더 큰 경우가 있을것이니..
//				x = mid;
				x = Math.max(x, mid);
				start = mid+1;
				
			} else if ( sum > N) { //랜선수가 너무 많으니 X를 키워서 크게크게 자르자.
				start = mid+1;
				
				//현재까지의 가장 최대 X 값 기록
				x = Math.max(x, mid);
			} else {
				end = mid-1;
			}
		}
		
		System.out.println(x);
	}

}