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

조건

1. 가지고 있는 랜선의 개수는 K이다.

2. 필요로하는 랜선의 개수는 N이다.

3. 랜선의 최대값이 int 형의 최대 값이기 때문에 long으로 탐색한다.

4. K개의 랜선의 길이를 받고 그 값에서 필요로 하는 N개를 충족하며 최대길이의 랜선을 출력하면된다.

예제 입력

해설

랜선의 최소 길이에서 부터 최대 길이 까지의 범위를 가진채 이분탐색을 통해 해당 값으로 / 를 해보고 개수에 충족이 된다면 해당 길이의 값을 저장한 후 L <= R 될때 까지 이분 탐색을 실행한다.
그리고 최종적으로 저장된 값이 개수를 충족하는 최대 길이의 랜선이니 저장값을 출력하면 정답이 나온다.

코드

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



public class Main {
	
	static int K,N;
	static int[] A;
	
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();

	static void input() {
		
		K = scan.nextInt(); // 가지고 있는 랜선의 개수를 받는다.
		N = scan.nextInt(); // 필요로 하는 랜선의 개수를 받는다.
		A = new int[K+ 1]; //index 시작을 1로 하기 위해 N+1을 해준다.
		for(int i=1;i<=K;i++) { //K의 값들을 받아준다.
			A[i] = scan.nextInt(); 
		}
	
	}

	
	static boolean findAns(long len) {
		long sum =0;
		for(int i = 1;i<=K;i++) {
			sum +=  A[i] / len; // 이분 탐색으로 정해진 값에서 가진 랜선의 길이들을 나							   // 눠 필요로 하는 개수가 충족되는지를 확인한다.
		}
		return sum >= N;

	}
	
	static void find() {
		long L = 1, R = Integer.MAX_VALUE,ans=0; // 이분 탐색 범위를 정해준다.
		while(L<=R) {
			long mid = (R + L) /2;
			if(findAns(mid)) { // 개수를 충족한다면 해당 값은 ans에 저장후 다음 이분탐								// 색을 시작한다.
				ans = mid;
				L = mid +1;
			}else {
				R = mid - 1;
			}
		}
		System.out.println(ans); // 저장되어 있는 mid값을 출력한다.
		}

		
		
	public static void main(String[] args) {
		input();
		find();
	}
	
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}
		
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		Long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			}catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}