1. 문제 설명 📌

문제 링크

일반적인 매개변수 탐색이나 이분 탐색 문제보다 까다로웠던 점은,

1️⃣ 통나무의 자를 수 있는 위치가 정해져 있다.
2️⃣ 통나무의 가장 긴 조각을 작게 만들었을 때, 제일 처음 자른 위치도 같이 출력 해라.

였다. 이걸 유념하며 문제를 풀어야 한다.

2. 구현 방법 🗃️

KEY WORD: Parametric Search, Binary Search, Greedy Algorithm

0️⃣ 통나무를 자를 수 있는 위치를 받아서 오름차순으로 정렬한다.
1️⃣ 이분탐색으로 통나무의 가장 긴 조각의 최소값을 구한다. 구하는 방법은 다음과 같다.
- 1️⃣-1) f(w) = 모든 조각난 통나무의 길이가 w 이하인가? 라는 결정문제 함수를 만든다. 이를 만족하는 f(w) 중 가장 오른쪽에 있는 f(w)의 w가 바로 답이다. (매개 변수 탐색)
- 1️⃣-2) 통나무를 자를 때, 역순으로, 자를 수 있는 위치의 가장 오른쪽부터 시작한다. (최초로 자르는 위치를 따로 계산하지 않기 위함)
- 1️⃣-3) 만약 자를 수 있는 횟수가 남았는데, 이미 모든 조각난 통나무의 길이가 w 이하라면, 최초 자르는 위치는 제일 오른쪽으로 갱신한다.
- 1️⃣-4) 만약 자를 수 있는 횟수를 다 썼다면, 마지막 자른 곳을 최초 자르는 위치로 저장하고 멈춘다.
2️⃣ 매개 변수 탐색으로 찾은 W와 first_cut(최초 자르는 위치)를 출력 한다.

(1) 시간복잡도 분석 🕓

통나무의 길이: L, 자르는 위치의 개수: K, 자를 수 있는 횟수: C

정렬: $O(K \log K)$
f(w) 계산: $O(K)$
이분 탐색: $O(log_2 L)$

결론: $O(K \log K + log_2 L)$

K는 최대값이 10_000이라 SAFE, L이 10억이긴 하지만, $log_2 L = 29.xxx$ 따라서 이것도 SAFE

3. 코드 소개 🔎

(1) SUDO CODE

이분탐색 {
    1. mid 값 구하기;
    2. 모든 조각난 통나무의 길이가 mid 값 이하가 되는가? = f(d) 확인;
    3. 되면 mid 상향 조정, 안되면 mid 하향 조정
}

f(w 너비,c 자를 수 있는 횟수) = 이분탐색 2번에 해당하는 함수 {
    0. prev: 이전 통나무 자른 위치, now: 현재 통나무 자를 위치;
    1. 모든 자를 수 있는 위치를 역순으로 조회한다. 따라서 항상 (prev > now)인 상태이다.;
    2. prev - now <= w 이면은 c(자를 수 있는 횟수)가 남아있다면 now로 first_cut(최초 자르는 위치) 갱신;
    3. prev - now > w 라면
        c를 다 썻다. false 반환
        now를 이전 위치에 다시 둬본다. ➜ 그래도 안됨. w로는 안된다. false 반환;
        now를 이전 위치로 두려 했더니, 이전 위치가 더 이상 없다. false 반환;
        now를 이전 위치로 뒀을 때, prev - now <= w 가 된다면 c 하나 차감. prev = now 넣고 다시 반복;
    4. 모든 위치를 다 돌았는데 아직 false 반환하지 않았다. ➜ w는 가능하다. true 반환
}

(2) JAVA CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    static long L;
    static int K,C;
    static long FIRST_CUT = Long.MAX_VALUE;
    static long [] loc;
    public static void main(String[] args) throws IOException {
        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        L = Long.parseLong(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        loc = new long [K + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= K; i++) {
            loc[i] = Integer.parseInt(st.nextToken());
        }
        loc[0] = 0;
        // 계산
        Arrays.sort(loc);
        System.out.println(binary_search() + " " + FIRST_CUT);
    }

    // 통나무의 가장 긴 조각의 최소값을 출력
    public static long binary_search () {
        long start = 0;
        long end = L;
        while (start <= end){
            long mid = start + (end - start)/2;
            if(f(mid, C)) end = mid - 1;
            else start = mid + 1;
//            System.out.println("--------------");
        }
        return start;
    }

    // w 이하로 모든 통나무를 자를 수 있는가?
    public static boolean f(long w, int c){
//        System.out.println("너비: " + w);
        long prev = L;
        long first_cut = -1;
        for (int i = K; i >= 0; i--) {
            long now = loc[i];
            if(prev - now <= w){
                if(now != 0 && c > 0) first_cut = now;
            }
            else{
//                System.out.println(now);
                if(i == K) return false;
                now = loc[++i];
                if(prev - now <= w) {
                    if(c == 0) return false;
                    c--;
                    prev = now;
                    if(now != 0) first_cut = now;
//                    System.out.println("first_cut: "+first_cut);
                }else return false;
            }
        }
        FIRST_CUT = first_cut;
        return true;
    }
}