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

 

이분탐색을 이용한 문제이다. 문제의 접근 방법을 잘 몰라서 구글링을 통해 문제 해결방법을 보았고, 그 이후에 문제를 풀었다. 가장 큰 인덱스 값을 끝 값으로 두고 이분탐색을 진행하면 쉽게 해결이 가능하다. 이 문제에서 처음에 답이 제대로 나왔는데 틀려서 보니 N의 범위가 상당히 컸다. 따라서 n의 입력값과 n을 이용하는 값들을 모두 long형으로 변경하여서 문제를 해결할 수 있었다.

 

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

public class p1654 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int a = Integer.parseInt(st.nextToken());
		long b = Long.parseLong(st.nextToken());
		int[] ary = new int[a];
		long max = 0;
		for (int i = 0; i < a; i++) {
			ary[i] = Integer.parseInt(br.readLine());
			if (ary[i] > max) {
				max = ary[i];
			}
		}
		long start = 1;
		long end = max;

		while (start <= end) {
			long num = 0;
			long mid = (start + end) / 2;

			for (int i = 0; i < a; i++) {
				num += ary[i] / mid;
			}

			if (num >= b) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		System.out.println(end);
	}
}