통나무 자르기 (1114번) - 백준 (BOJ)

https://www.acmicpc.net/problem/1114

1114번: 통나무 자르기

 

 

백준 - 통나무 자르기 (1114번)

 

난이도 : Gold 1

알고리즘&자료구조 : Parametric Search (파라메트릭 서치) & Sorting (정렬)

시간복잡도(Time Complexity) : O( K * logK )

---

파라메트릭 서치를 적절히 활용해서 풀 수 있는 문제이다.

 

< 전체 코드 >

class Log():
    def __init__(self, L, K, C):
        acc = sorted(set(map(int, input().split())))
        while acc and acc[-1] == L:
            acc.pop()
        acc.append(L)
        arr = acc[:]
        K = len(arr)
        s, e = arr[0], L
        for i in range(K-1):
            arr[i+1] = acc[i+1] - acc[i]
            s = arr[i+1] if arr[i+1] > s else s
        arr = arr[::-1]
        C += 1
        self.K, self.arr = K, arr
        if C < K:
            while s < e:
                m = (s+e)>>1
                i = self._packing(m, C)
                if i < K:
                    s = m+1
                else:
                    e = m
        acc = arr[:]
        for i in range(K-1):
            acc[i+1] = acc[i] + arr[i+1]
        i = self._packing(s, C-1)
        loc = arr[-1] if i == K else L-acc[i-1]
        self.answer = (s, loc)


    def _packing(self, size, C):
        pack = i = cur = 0
        while i < self.K and pack < C:
            while i < self.K and cur + self.arr[i] <= size:
                cur += self.arr[i]
                i += 1
            pack += 1
            cur = 0
        return i

    
if __name__ == '__main__':
    log = Log(*map(int, input().split()))
    print(*log.answer)

---

 

① 자를 수 있는 좌표들 중,

중복된 좌표 및 통나무 전체 길이 L 좌표를 제거하고 오름차순으로 정렬한다.

그리고 오른쪽 끝에 L을 추가해준다.

 

acc = sorted(set(map(int, input().split())))
while acc and acc[-1] == L:
    acc.pop()
acc.append(L)

 

 

 

② 통나무를 K개의 좌표에서 모두 잘랐을 때 만들어지는

각 통나무들의 길이를 배열 arr에 담는다.

그리고 arr을 거꾸로 뒤집는다. (뒤집는 이유는, 나중에 통나무를 자르는 첫 번째 좌표를 찾기 위해서이다.)

s는 가장 긴 통나무 조각의 길이가 된다.

 

arr = acc[:]
K = len(arr)
s, e = arr[0], L
for i in range(K-1):
    arr[i+1] = acc[i+1] - acc[i]
    s = arr[i+1] if arr[i+1] > s else s
arr = arr[::-1]

 

 

 

③ 현재 설정한 길이 size에서,

통나무를 몇 개로 쪼갤 수 있는지 세기 위한 함수 _packing을 생성한다.

 

def _packing(self, size, C):
    pack = i = cur = 0
    while i < self.K and pack < C:
        while i < self.K and cur + self.arr[i] <= size:
            cur += self.arr[i]
            i += 1
        pack += 1
        cur = 0
    return i

 

 

 

④ start = s, end = L 로 두고 범위를 좁혀나가면서

Parametric Search 를 진행한다.

 

( while s < e: ) 반복문이 종료됐을 때의 s 값이,

가장 짧게 만든 가장 긴 조각의 길이가 된다.

 

C += 1
self.C, self.K, self.arr = C, K, arr
if C < K:
    while s < e:
        m = (s+e)>>1
        i = self._packing(m)
        if i < K:
            s = m+1
        else:
            e = m

 

 

 

④ 첫 번째로 통나무를 자르게 되는 좌표를 찾고,

위에서 찾은 s와 함께 반환한다.

 

acc = arr[:]
for i in range(K-1):
    acc[i+1] = acc[i] + arr[i+1]
i = cur = pack = 0
while i < K and pack < C-1:
    while i < K and cur+arr[i] <= s:
        cur += arr[i]
        i += 1
    pack += 1
    cur = 0
loc = arr[-1] if i == K else L-acc[i-1]
self.answer = (s, loc)