1654 랜선 자르기

---

https://www.acmicpc.net/board/view/67789

글 읽기 - 자바) 두가지 방법의 이분탐색 차이점

 

 

 

---

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


public class Main {
	static long []arr;
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int K = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		arr = new long[K];
		long max = 0;
		for(int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Long.parseLong(st.nextToken());
			max = Math.max(max, arr[i]);
		}
		System.out.println(binary_search(max));
	}
	static long binary_search(long max) {
		long start = 1;
		long end = max;
		while(start <= end) {
			long mid = (start + end) / 2;
			int sum = 0;
			
			for(long lan : arr) {
				sum += (lan / mid);
			}
			if(sum < N)
				end = mid -1;
			else
				start = mid + 1;
		}
		return end;
	}
}

 

 

 

 

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


public class Main {
	static long []arr;
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int K = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		arr = new long[K];
		long max = 0;
		for(int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Long.parseLong(st.nextToken());
			max = Math.max(max, arr[i]);
		}
		System.out.println(binary_search(1,max));
	}
	static long binary_search(long start, long end) {
		if(start > end) { //재귀 종결 조건
			return end;
		}
		long mid = (start + end) / 2;
		int sum = 0;
		for(long lan : arr) {
			sum += lan/mid;
		}
		if(sum < N)
			return binary_search(start, mid-1);
		else
			return binary_search(mid+1, end);
	}
}