백준 - 1654번 - 랜선 자르기

1654번

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

public class Main{

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st  = new StringTokenizer(bf.readLine());
		int k = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());

		int[] arr = new int[k];

		long max = 0;

		for (int i = 0; i<k; i++) {
			arr[i] = Integer.parseInt(bf.readLine());
			if (max < arr[i]) {
				max = arr[i];
			}
		}

		max++;
		long min = 0;
		long mid = 0;

		while (min<max) {
			mid = (min+max) / 2;

			long cnt = 0;
			for (int i = 0; i<arr.length; i++) {
				cnt += (arr[i] / mid);
			}

			if (cnt < n) {
				max = mid;
			}
			else {
				min = mid +1;
			}
		}

		System.out.println(min-1);
	}
}

풀이

---

이분탐색을 응용한문제다.

랜선을 k개 가지고 있는데 잘라서 n개를 만들때 최대길이는 무엇인지 구하는문제다.

이분탐색 문제이기에 가지고 있는 k개의 랜선중 제일 긴선의 길이의 반을 중간값으로 잡고 계속 비교해나가야 한다.

갯수가 n보다 작으면 mid값을 max값으로 잡는다
갯수가 n보다 크거나 같으면 mid+1를 min으로 잡는다

이렇게 계속해가다 보면 min이 max보다 크거나 같게 된다.
그때 min값에-1을 해주어 출력하면된다.

Upper Bound방식
https://st-lab.tistory.com/267