문제 이해

길이가 다른 여러 개의 선이 존재한다.
이 선들을 잘라서 모두 같은 길이의 선으로 만들고 싶다.
동등한 길이의 선으로 만들 수 없는 짜투리 선들은 버린다.(재활용 불가)
(ex) 2m짜리 선을 만들고 싶을 때, 3m선으로는 2m를 만들고 남은 1m는 버림)

이 때 나는 N개 이상의 동등한 길이의 선을 만들고 싶다.
동등한 선의 길이를 K라고 할 때, K의 최댓값을 구하는 문제이다.

문제 풀이

T 길이의 선으로 동등한 길이의 선은 몇 개 만들 수 있을까.

내가 지정한 동등한 선의 길이가 K일 때, T / K만큼일 것이다.
JAVA에서 나누기는 '몫'을 의미하기 때문에, 나머지는 자동으로 버려지고 이는 짜투리 선을 재활용하지 않는 것까지 자동으로 수행한다.

즉, 내가 만든 동등한 길이의 선 개수 num = $\sum{\frac{arr[i]}{K}}$

1. num >= N : 정답이 될 가능성이 있다.
   우리는 K의 최댓값을 구하고 싶기 때문에 K를 키워야 하고, left를 변경한다.

2. num < N : 정답이 될 수 없다.
   num을 크게 해야하고, 나누기의 특성에 의해 K를 작게 해야 한다. 따라서 right을 변경한다.

이 때 K는 1 ~ N까지의 자연수 중 하나이기 때문에 원래 숫자 배열과 관계가 없고, 따라서 배열을 Sorting할 필요는 없을 것이다.

위와 같은 방법으로 이분 탐색을 수행해주었다.

코드

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

public class Main {
	static int K, N;
	static Long[] arr;
	
	static void max_length(Long right) {
        // 이분 탐색을 구현한 메서드
		long left = 1;
		long mid;
		long ans = 0;

		while(left <= right) {
			int sum = 0;
			mid = (left + right)/2;
			
			for(int i =0;i<K;i++) {
                // 문제 풀이에서 설명한 num을 구하는 방법
				sum += arr[i]/mid;
			}
			
			if(sum>=N) {
                // 문제 풀이 1번 상황
                // 답이 될 수 있으므로 저장(ans) & 값 증가(left값 변경)
				ans = mid;
				left = mid + 1;
			}
			else {
                // 문제 풀이 2번 상황. 값을 감소시켜야 함(right값 변경)
				right = mid - 1;
			}
		}
		System.out.println(ans);
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		K = sc.nextInt();
		N = sc.nextInt();
		arr = new Long[K];
		
		long max = Integer.MIN_VALUE;
		for(int i =0;i<K;i++) {
			arr[i] = sc.nextLong();
            max = Math.max(max, arr[i]);
		}
		
		max_length(max);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

결과

• 3번째 줄 틀렸습니다 : 랜선의 최댓값은 Integer의 범위를 넘어선다. 따라서, Long형으로 처리했어야 했는데, int형으로 처리하여 틀렸다.