백준 문제풀이 - 1114 번

링크 -> https://www.acmicpc.net/problem/1114

1. 요약 및 풀이방법

통나무를 정해진 위치에서만 자를 수 있고,
자를 수 있는 최대 횟수가 정해져 있을 때,
가장 긴 조각이 작도록 자르는 방법을 찾는 문제입니다.

최근 풀었던 문제중 가장 고민도 많이하고, 시간도 오래 걸리고, 많이 틀렸던 문제입니다.
문제의 조건 중 가능한 것이 여러 가지라면 처음 자르는 위치가 작은 것을 출력하도록 하기 때문에 뒤에서부터 거꾸로 진행해야 함을 늦게 깨달았습니다.
풀이한 문제의 코드를 가다듬고 하는데에도 많은 코드를 참고했습니다.

문제는 다음과 같이 풀이합니다.
나무 조각 하나의 길이를 기준으로 하는 이분 탐색을 이용합니다.
나무조각 하나 길이의 범위는 0~L(통나무 전체의 길이) 이므로,
이 범위를 mid를 구해 이분탐색 합니다.

특정 mid를 기준으로 나무조각이 잘리는 갯수와, 처음 자르는 위치를 구하기 위해
solve 함수를 작성하였습니다.

뒤에서부터 자를 수 있는 위치마다 나무 조각의 길이를 누적합 하고,
값이 mid보다 커지면 이전 위치에서 자르고 count를 올립니다.

이렇게 잘려진 통나무의 count가 최대 횟수인 C보다 크면
너무 잘게 많이 잘렸다는 의미이므로, 각 조각의 크기를 키우는 방향으로 update합니다.

반대로 count가 C보다 작거나 같으면
더 잘게 자를 수 있다는 의미이므로, 각 조각의 크기를 줄이는 방향으로 update합니다.

2. Code

from sys import stdin

input = stdin.readline

def main():
    L, K, C = map(int, input().split())
    positions = [0, *sorted([*map(int, input().split())]), L]
    pieces = [positions[idx+1] - positions[idx] for idx in range(K+1)]
    longest = max(pieces)

    def solve(mid):
        if longest > mid:   # 현재 기준으로 자를 수 없는 나무 조각이 있는 경우.
            return 10001, 0
        sums_ = 0
        count = 0
        for piece in pieces[::-1]:
            sums_ += piece      # 나무조각 길이를 누적 합
            if sums_ > mid:     # 기준이 넘어가면
                sums_ = piece   # 새로운 조각으로 취급
                count += 1
        return count, sums_ if count == C else pieces[0]

    left = 0
    right = L
    while left <= right:
        mid = (left + right) // 2   # 나무조각 하나의 최대 길이

        count, front = solve(mid)
        if count <= C:              # 조각을 더 작게 자를 수 있는 방향으로 update
            ans_longest = mid
            ans_front = front
            right = mid - 1
        else:                       # 조각을 더 크게 자를 수 있는 방향으로 update
            left = mid + 1

    print(ans_longest, ans_front)

if __name__ == "__main__":
    main()

3. 학습 내용

이번 문제는 접근도, 이해도, 코드 작성도 모두 쉽지는 않았습니다.
따라서 다른 풀이도 많이 찾아보고 참고했습니다.
그리고 여러 코드를 찾아보면서 python에서 쉽게 사용할 수 있는 다양한 문법들도 참고하여 코드를 더욱 가시적이고 짧게 작성할 수 있었습니다.

4. 결과