백준 1654번
https://www.acmicpc.net/problem/1654

문제

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

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

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

---

생각하기

문제를 처음에 어떻게 풀어야 될 지 고민하다 이분 탐색을 사용하기로 했다.

가지고 있는 랜선에서 길이를 나누기 때문에 가장 긴 길이의 랜선을 먼저 기준으로 설정한다.
처음 시작하는 범위는 min=1, max=가장 긴 선의 길이 값 으로 설정해주고 이분 탐색을 실행하면 된다.

여기서 처음에 min을 0으로 두고 실행했었는데,
by zero 에러가 발생했다.

어떤 Testcase 때문에 저런 오류가 발생하는 지 찾아봤는데..

K=1 N=1
1

이라는 Testcase가 들어가면 by zero 에러가 발생했다.
모든 선의 길이가 1이라고 가정한다면 min이 0이 되고 과 max가 1이 되면서 중간값인 half가 0이 나오기 때문에 by zero에러가 발생하게 된다.

binary_search() 메소드 동작을 설명하자면
max와 min을 계속 값을 변경해주면서 범위를 줄여가면서 half값으로 원하는 값을 찾으면 된다.
while문을 사용해서 min <= max 조건으로 반복을 계속한다.

half 값을 기준으로 선들 길이로 만들어진 배열을 반복하면서 만들어진 갯수를 모두 더한값을
count변수에 집어넣고 count와 N을 비교한다.

만약 count > N 일 경우 원하는 갯수보다 잘라진 선들이 많다 를 의미하기 때문에
min, max, half 값을 다시 수정한다. 잘라진 선들이 원하는 선의 갯수보다 많다는 것은
결국 하나의 잘라진 선이 너무 짧다 -> 더 길게 만들 수 있다. 를 의미
이 경우 기존 범위에서 half보다 커야 하기 때문에 min = half + 1로 갱신해주고
max는 그대로 둔다.

또한, count < N 일 경우 원하는 갯수보다 잘라진 선들이 적다 를 의미하기 때문에
min, max, half 값을 다시 수정한다. 잘라진 선들이 원하는 선의 갯수보다 적다는 것은
결국 하나의 잘라진 선이 너무 길다 -> 더 짧게 만들어야 한다. 를 의미
이 경우 기존 범위에서 half보다 작아야 하기 때문에 max = half - 1로 갱신해주고
min는 그대로 둔다.

이런식으로 min 과 max를 수정하면서 범위를 계속 줄여 나가면 while 조건을 충족하지 못해서 빠져나가게 되고 마지막 (min + max)/2의 값이 정답이 된다.

문제를 푸는데 백준에서 만들어놓은 Testcase는 되는데도 불구하고,
제출시 계속 오답이 나와서 반례를 찾아보며 다른 Testcase를 많이 썼었다.

K	N	lines	result
1	1	1	1
3	8	97 40 64	21
4	5	10 1 1 1	2

---

코드

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

public class Main {
	
	// 자를 수 있는 선의 길이의 최대 길이를 찾는 메소드
	private static long binary_search(long arr[], int N, long max) {
		long half = 0;
		long min = 1;

		while(min <= max) {
			half = (min + max)/2;
			long count = 0;

			for(long num : arr) {
				count += num / half;
			}

			// 원하는 랜선 갯수 보다 잘라진 랜선 수가 적을경우
			// 하나의 랜선 길이가 길어서 길이를 더 짧게 만들어야 함 
			// half보다 아래의 수.
			if(count < N) {
				max = half-1;
			}
			// 원하는 랜선 갯수 보다 잘라진 랜선 수가 많을경우
			// 하나의 랜선 길이가 짧아서 더 길게 만들어야 함 
			// half보다 위의 수에 있음.
			else {
				min = half+1;
			}
		}
		return (max+min)/2;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int K = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		long result = 0;
		long max = 0;

		long [] arr= new long[K];
		for(int i=0; i<K; i++) {
			arr[i] = Integer.parseInt(br.readLine());
			max = Math.max(max, arr[i]);
		}

		result = binary_search(arr, N, max);

		System.out.println(result);
		br.close();
	}
}