썸네일 출처: https://ye-yo.github.io/thumbnail-maker/

---

📖 문제

1654번: 랜선 자르기

---

💡 아이디어

1. 가장 간단한 방식

랜선을 자를 수 있는 가장 이상적인 최대 길이부터 1씩 줄여가며 가장 처음으로 자르는 것이 가능한 길이를 찾아내면 그것이 최적값일 것이다.

가장 이상적인 경우는 모든 랜선이 남는 부분 없이 딱 잘라지는 경우이고, 이 경우 랜선 하나의 길이는 총 랜선 길이를 잘라야 하는 랜선 갯수로 나눈 값이다. 100, 200, 300짜리 랜선에서 6개의 랜선을 잘라야 하는 경우를 예로 들면 (100 + 200 + 300) / 6 = 100 이다.

이후 모든 랜선을 랜선 하나의 길이로 나눠보고, 나눈 값의 총합이 필요한 랜선의 개수보다 크거나 같으면 그 랜선의 길이가 랜선을 자를 수 있는 최대 길이가 된다.

하지만, 이 경우 최악의 경우 시간복잡도는 O(R*K)(R은 랜선의 최대 길이) 이고 랜선의 길이 R은 2의 31승 보다 작은 자연수, 랜선의 개수 K는 최대 10,000이므로 최악의 경우 대략 10의 15승이 넘어가는 연산을 해야 한다.

2. 이분 탐색 활용(Parametric Search)

랜선을 자를 수 있는 최대 길이를 X라고 할때, X에 대해 이분탐색을 적용하면 시간복잡도를 획기적으로 줄일 수 있다. X를 최대부터 하나씩 줄여가며 탐색하는것이 아니라, 최솟값과 최댓값 사이의 중앙값을 이용해서 탐색한다.

만약 중앙값을 이용해서 랜선을 개수만큼 자르는 것이 가능하다면 그보다 더 작은 값들은 탐색할 필요가 없다. 중앙값이 가능한 최소 길이가 되기 때문이다. 반대로 불가능하다면 그보다 더 큰 값들은 탐색할 필요가 없다. 그보다 큰 값들은 반드시 불가능하기 때문이다.

따라서 탐색 범위를 매번 2분의 1로 줄여가며 탐색할 수 있고, 시간복잡도는 O(logR*K)가 된다.

이런식으로 리스트의 아이템이 아닌 파라미터를 이용해서 이분탐색하는 것을 매개 변수 탐색(Parametric Search)이라고 한다.

---

⏱️ 최적화

랜선이 어떤 길이로 나눌 수 있는지 확인할 때, 미리 버릴 수 있는 최대 길이를 계산한 후 총 나머지의 합이 그것을 초과하는지 확인하면 모든 랜선에 대해 나누기 연산을 하기 전에 그 랜선 길이가 가능한 길이인지 확인할 수 있다.

예를 들어, 100, 200, 300짜리 랜선을 10개로 나눠야 할 때 55가 가능한 랜선의 길이인지 확인하려면, 우선 버릴수 있는 최대 길이를 계산한다. 55 * 10 = 550이고, 랜선 길이의 총 합이 600이므로 버릴 수 있는 최대 길이는 600 - 550 = 50이다.
이제 첫 랜선부터 랜선 길이로 나눠서 버리는 길이의 총 합을 계산한다. 첫 번째 랜선은 55짜리 1개를 얻고 나머지 45를 버려야 한다. 두 번째 랜선은 55짜리 3개를 얻고 나머지 35를 버려야 한다. 이때 버리는 총 합은 80으로 50을 넘어가므로 이 경우는 불가능한 경우임을 바로 알 수 있다.

---

✏️ 코드

use std::cmp::{max, min, Ordering};
use std::io::{stdin, stdout, BufWriter, prelude::*};

const N_MAX: usize = 1_000_000;
const K_MAX: usize = 10_000;

fn main() {
    solve();
}

fn solve() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().flat_map(str::parse::<u64>);
    
    // -- test case --
    // let mut rng = thread_rng();
    // let mut input: Vec<u64> = vec![K_MAX as u64, rng.gen_range(K_MAX..N_MAX) as u64];
    // for _ in 0..K_MAX {
    //     input.push(rng.gen_range(0..2_000_000_000));
    // }
    // let mut input = input.into_iter();

    let (k, n) = (input.next().unwrap() as usize, input.next().unwrap());
    let mut nums = [0u64; K_MAX];
    let mut sum = 0u64;
    for num in nums.iter_mut().take(k) {
        *num = input.next().unwrap();
        sum += *num;
    }

    let mut start = 1u64;
    let mut end = sum / n + 1;
    let mut max_len = u64::MIN;
    'outer: while start < end {
        let middle_len = start + (end - start) / 2;
        let leftover = sum - (middle_len * n);
        let mut leftover_sum = 0u64;

        // can't divide
        for num in nums.iter().take(k) {
            leftover_sum += *num % middle_len;
            if leftover_sum > leftover {
                end = middle_len;
                continue 'outer;
            }
        }
        // can divide
        max_len = max(middle_len, max_len);
        start = middle_len + 1;
    }

    println!("{max_len}");
}