[백준 1114] 통나무 자르기 (파이썬 / Python)

---

📑 문제

문제링크 : 통나무 자르기

---

🤔 처음 생각

맨 처음에 가능한 최대길이의 최솟값은 max_len = ceil(L / (max(C, K) + 1)) 이상이어야 한다고 생각했습니다. 그래서 통나무를 모두 토막낸 후 max_len 길이로 자를 수 있는 위치를 찾아가며 구하려고 했습니다.

그런데 자를 수 있는 위치에 따라 max_len 길이의 토막이 없을 수도 있으며, 특정 길이로 자를 수 있는 위치를 전 범위에서 구하기에는 시간 복잡도가 $O(K^2)$ 이며, 줄이기 위해서는 DP까지 써야하는 등 너무 복잡해진다고 생각했습니다.

그리고는 이분탐색으로 눈을 돌리게 됐습니다.

---

🎯 풀이방법

Greedy, 이분탐색 문제이며, 시간복잡도는 $O(K \log L)$ 입니다.

arr : 시작점과 끝지점을 포함한 자를 수 있는 위치가 담긴 리스트

pieces : 자를 수 있는 모든 지점을 잘랐을 때의 길이들이 역순으로 담긴 리스트

cut(length): 통나무를 length 이하의 길이로 자르는 함수로, 자른 횟수와 처음으로 자르는 위치를 return 해줌

left & right : 잘라야하는 최대 길이를 구하기 위한 이분탐색의 왼쪽과 오른쪽

1. 자를 수 있는 지점들을 입력받아 모두 잘랐을 때 모든 토막의 길이가 어느 정도인지 구합니다.

2. 통나무를 잘랐을 때 각 토막의 길이의 최대값이 최소가 되도록 이분탐색을 진행해야 합니다.

3. left = 0, right = L 부터 시작해서 길이가 통나무 길이를 mid = (left + right) // 2 로 잘랐을 때 몇 번 잘라야하는지 확인합니다.

   1. C번 이하로 자를 수 있다면, 길이를 최소 mid 이하로 자를 수 있다는 뜻입니다. 따라서 다음 탐색에서 더 짧은 길이를 탐색하기 위해 right = mid - 1 을 해줍니다.

   2. C번 초과로 잘라야한다면, 길이를 최소 mid 보다는 커야한다는 뜻입니다. 따라서 다음 탐색에서 더 긴 길이를 탐색하기 위해 left = mid + 1 을 해줍니다.

4. cut(length) 함수에서는 최대 길이가 length 이하가 되도록 잘라야 하며, 잘라야하는 가장 앞 위치를 반환해야 합니다.

   1. pieces 의 원소들을 누적합을 해가며 잘라줍니다. 만약 누적합의 값이 length 이하이면 자르지 않고 다음으로 넘어갑니다. 만약 length보다 커진다면 이전 위치에서 잘라줍니다.

   2. pieces 의 원소들을 역순으로 탐색해가며 잘라야합니다. 그래야 절단해야하는 가장 앞 위치를 알아낼 수 있습니다.

   3. 모두 잘랐을 때, 자른 횟수가 C번 미만이라면 자를 수 있는 첫 번째 위치를 잘라줄 수 있습니다.

5. 위 과정을 left <= right일 동안 진행하여 답을 구해줍니다.

---

🔎 유의할 점

• 자를 수 있는 위치들을 입력받고 정렬해주어야 합니다. 그래야 모두 잘랐을 때의 각 토막의 길이들을 제대로 알 수 있습니다.

• cut(length) 함수에서 각 토막들을 역순으로 탐색해주어야 합니다. length 이하로 몇 번을 잘라야하는지는 역순으로 탐색하지 않아도 알 수 있지만, 처음으로 절단해야 하는 위치를 알기 위해서는 역순으로 탐색해야만 합니다.

• C번 미만으로 자른 경우, 자를 수 있는 위치의 맨 앞을 잘라주어야 합니다. 방법이 여러 가지인 경우 처음 자르는 위치가 가장 작아야 하므로, 가능한 절단 위치에서 한 번 더 잘라주어야 합니다.

---

💻 코드

from sys import stdin

input = stdin.readline


def solve():
    L, K, C = map(int, input().split())
    arr = [0, *sorted([*map(int, input().split())]), L]
    pieces = [arr[i] - arr[i-1] for i in range(len(arr) - 1, 0, -1)]
    longest_piece = max(pieces)

    def cut(length):
        if longest_piece > length:
            return 10001, 0

        cur_len = 0
        count = 0
        for piece_len in pieces:
            cur_len += piece_len
            if cur_len > length:
                cur_len = piece_len
                count += 1

        return count, cur_len if count == C else pieces[-1]

    left, right = 0, L
    ans_pt, ans_len = 0, 0
    while left <= right:
        mid = (left + right) // 2
        cnt, pt = cut(mid)
        if cnt <= C:
            ans_pt = pt
            ans_len = mid
            right = mid - 1
        else:
            left = mid + 1

    return ans_len, ans_pt


if __name__ == '__main__':
    print(*solve())