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

1114번: 통나무 자르기

 

코드

l, k, c = map(int, input().split())
points = [0]+sorted(list(map(int, input().split())))+[l]
pieces = [points[i+1]-points[i] for i in range(k+1)]
longest = max(pieces)


def chk(length):  # 최대 길이
    if longest > length:  # 가능한 최대 길이보다 더 긴 통나무가 있는 경우
        return [10001, -1]
    tmp = 0 # 통나무 조각 길이 합
    cutting = 0 # 자른 횟수
    for p in pieces[::-1]:
        tmp += p
        if tmp > length:    # 이번 조각을 더하면 l보다 길어지게 되는 경우
            cutting += 1
            tmp = p # 새로운 조각 시작
    return [cutting, tmp if cutting == c else pieces[0]]

# 매개 변수 탐색
s, e = 0, int(1e9)
ans = []
while s <= e:
    mid = (s+e)//2
    cutting, first = chk(mid)
    if cutting <= c:
        ans = [mid, first]
        e = mid-1
    else:
        s = mid+1
print(*ans)

 

매개 변수 탐색에서 사용될 조건을 확인하기 위한 함수 chk(length)는 전체 통나무를 몇개의 조각으로 자를 수 있는지와 그 때 처음 자른 위치를 리턴한다.

 

만약 가능한 최대 길이 제한인 length보다 자를 수 있는 통나무 조각의 길이가 길다면 불가능하다는 뜻으로 [10001, -1]을 리턴해준다.

 

통나무의 왼쪽 끝이 아닌 오른쪽 끝부터 자르기 때문에 왼쪽에서 첫번째 조각 부분이 처음으로 통나무를 자른 위치라고 할 수 있다. 그런데 딱 C번 자른다면 첫번째 조각이 아닌 tmp가 왼쪽에서부터 첫번째로 통나무를 자른 위치라고 할 수 있다.