[백준] 1654 랜선 자르기 - Java

 

 

 

매개 변수 탐색을 활용해 풀 수 있는 문제이다.

 

만들 수 있는 최대 랜선의 길이를 구하시오.

=>

특정 길이로 잘랐을 때 N개보다 많은 랜선을 얻을 수 있는가?

 

 

각 랜선의 길이는 정수 범위 안에서 결정된다.

 

랜선을 자르고 답을 갱신하다 보면 정수 범위를 초과할 수도 있을 것 같다. long타입으로 설정하고 풀자.

 

 

import java.util.*;
import java.io.*;

public class Main {

	static int N;
	static int K;
	
	static int LAN[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		K = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());

		LAN = new int[K + 1];		

		for (int i = 1; i < K + 1; i++) {
			LAN[i] = Integer.parseInt(br.readLine());
		}

		System.out.println(solve());


	}

	static long solve(){
		long L = 1; 
		long R = Integer.MAX_VALUE;
		long ans = 0;

		while(L <= R){
			long mid = (L + R) / 2;
			if(cut_check(mid)){
				ans = mid;
				L = mid + 1;
			}else{
				R = mid - 1;
			}
		}

		return ans;

	}

	static boolean cut_check(long cut){
		long sum = 0;
		for(int i = 1; i< K + 1; i++){
			sum = sum + LAN[i] / cut;
		}

		if(sum >= N){
			return true;
		}else{
			return false;
		}

	}


}