177. 1654(랜선 자르기) - 자바

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

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();
		long N = sc.nextInt();
		long[] lanLine = new long[K];

		for (int i = 0; i < K; i++) {
			lanLine[i] = sc.nextLong();
		}

		long start = 1;
		Arrays.sort(lanLine);
		long end = lanLine[lanLine.length - 1];

		while (end - start >= 0) {
			long mid = (end + start) / 2;
			long lines = 0;

			for (long val : lanLine) {
				lines += val / mid;
			}

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

문제요약

주어진 랜선들로 원하는 개수만큼의 랜선을 최대한 크게 잘라보아라.

설명

문제를 처음보면 무슨소리인가 라는 생각이 들 것 이다.

문제를 풀어서 설명해보면

K개의 랜선을 가지고 있는데 N개로 만들려고한다.

K개의 랜선을 같은 길이로 잘라 N개를 만드는데 자를때 가장 긴 길이로 만들라는 뜻이다.

 

백준에 있는 예제를 가지고 이분탐색을 이용하여 문제를 풀어보겠다.

802 / 743 / 457 / 539 길이의 랜선이 있고 이를 자를 수 있는 경우의 수는 1cm ~ 802cm 이다.

여기에 이분탐색을 이용해보자.

start는 1 end는 802로 설정하고 이 둘을 더해 2 나눈 403이 mid값으로 설정된다.

		long start = 1;
		Arrays.sort(lanLine);
		long end = lanLine[lanLine.length - 1];

		while (end - start >= 0) {
			long mid = (end + start) / 2;
			long lines = 0;

			for (long val : lanLine) {
				lines += val / mid;
			}

을 통해 나온 랜선의 개수 총합이 만약 N보다 크거나 같다면 mid를 중심으로 오른쪽이라는 이야기로 start 값을 mid +1로 바꿔주면 된다.

 

반대로 N보다 작다면 mid를 중심으로 왼쪽이라는 이야기로 end값을 mid -1로 해주면 된다.

 

이런식으로 이어가다보면 start가 end보다 커지는 상황이 발생한다.(mid로 나눈 랜선의 개수가 N보다 크거나 같을 때, start만 조절하기 때문이다.)

			if (lines >= N) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}

 

그 때 end가 N개의 선을 만족시키고, 자를 수 있는 가장 큰 랜선의 길이이다.

		System.out.println(end);