백준 1654 - 랜선 자르기 (자바 - 이분탐색)

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

* 문제 요약

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm짜리 랜선에서 140cm짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이 만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.

이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 갯수 K, 그리고 필요한 랜선의 갯수 N이 입력된다. K는 1이상 10,000 이하의 정수이고, N은 1이상 1,000,000 이하의 정수이다.

그리고 항상 K <= N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다.

랜선의 길이는 2^31 - 1 보다 작거나 같은 자연수이다.

 

* 출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

 

* 예시

 

* 해결 과정

자를 수 있는 랜선 길이의 최소, 최대를 범위로 설정해서 매개변수 탐색을 수행하여 풀 수 있는 문제이다.

여기서 매개변수 탐색이란 오름차순 정렬된 배열과 같은 자료구조를 대상으로 특정 조건에 맞는 인덱스를 범위를 절반씩 줄여가며 찾는 이분탐색과는 조금 다른 개념의 알고리즘으로, 어떤 시점까지는 조건을 만족하지만 그 시점 이후로는 조건을 만족하지 않는 경우에서 최대값 찾기(Upper Bound), 어떤 시점까지는 조건을 만족하지 않지만 그 시점 이후로는 조건을 만족하는 경우에서 최소값 찾기(Lower Bound) 등 문제에서 최종적으로 찾고자 하는 최소값/최대값을 탐색하는 알고리즘이다.

 

이 문제에서는 자를 수 있는 랜선의 길이 중 최소값인 1을 start, 입력받은 랜선 중 길이가 가장 긴 랜선의 길이를 end 로 하여 다음과 같이 매개변수 탐색을 수행해주자.

1. start <= end 조건을 만족하는 동안 다음과 같은 로직을 수행해준다.

  - mid 를 (start + end) / 2 로 초기화한다. 여기서 mid 는 입력받은 랜선들을 자를 공통된 길이값에 해당한다.

  - 앞에서 입력받은 모든 랜선들에 대해 mid 값 만큼 나눴을 때 나오는 몫을 sum 변수에 합산해준다.

  - 모든 랜선들에 대해 mid 만큼 나누어 준 다음 최종적으로 나온 sum 값이 필요한 랜선 갯수 n보다 작다면 end 를 mid - 1 로 초기화하여 mid 값이 더 작아지는 방향으로 범위를 줄여준다.

  - 반대로 sum 값이 필요한 랜선 갯수 n보다 크거나 같다면 정답 변수 result 에 현재 mid 값을 저장해주고난 다음, start 를 mid + 1 로 초기화하여 mid 값이 더 커지는 방향으로 범위를 줄여준다.

2. 반복문이 끝나고 나면 result 를 출력 시켜준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws IOException {
		new Main().solution();
	}

	private void solution() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] inputArray = br.readLine().split(" ");
		int curline = Integer.parseInt(inputArray[0]);
		int reqline = Integer.parseInt(inputArray[1]);
		long[] lineArray = new long[curline];

		long max = 0;
		for (int i = 0; i < curline; i++) {

			long length = Long.parseLong(br.readLine());
			lineArray[i] = length;
			if (max < length)
				max = length;
		}

		long start = 1;
		long end = max;
		long mid = 0;
		long result = 0;
		while (start <= end) {
			mid = (start + end) / 2;

			long sum = 0;
			for (int i = 0; i < lineArray.length; i++) {
				long line = lineArray[i];

				long cutCount = line / mid;
				sum += cutCount;
			}

			if (sum < reqline) {
				end = mid - 1;
			} else {
				result = mid;
				start = mid + 1;
			}
		}

		bw.write(result + "\n");
		bw.flush();
		bw.close();
		br.close();
	}
}

 

자를 수 있는 랜선의 최소, 최대 길이를 범위로 설정하여 중간값을 기준으로 랜선을 자를 때 필요한 만큼 자를 수 있는지 없는지에 따라 범위를 절반씩 줄여가며, 필요한 만큼 자를 수 있는 공통된 길이 중 최대값을 구해주었으므로 매개변수 탐색 문제에 해당한다.