통나무 자르기 성공
벌목꾼 백은진은 나무를 종이 공장에 옮겨야 한다. 하지만, 통나무의 길이가 너무 길어서 트럭에 들어가지 않으므로, 여러개의 조각으로 나누려고 한다.
통나무의 길이는 L이고, K개의 위치에서만 자를 수 있다. 통나무를 자를 수 있는 위치가 주어진다. 이 위치는 통나무의 가장 왼쪽에서부터 떨어진 거리이다. 통나무를 자를 수 있는 횟수는 최대 C번이다.
통나무의 가장 긴 조각을 작게 만들고, 그 길이를 구해보자.
입력
첫째 줄에 세 정수 L, K, C가 주어진다. 둘째 줄에는 통나무를 자를 수 있는 위치가 주어진다.
출력
첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출력한다.
풀이
이 문제를 읽어보고 나서 가장 먼저 떠올린 풀이가 바로 이진탐색입니다. 수의 크기가 매우 크기 때문에 이진탐색을 이용하면 금방 적절한 나무토막의 크기를 찾을 수 있을것입니다.
가장 작은 통나무는 1이고, 가장 큰 통나무는 잘리지 않은 전체 크기일 수 있겠죠.
이제, 이진탐색을 수행해야 하는데 아직은 조금 모호합니다. 여기서 조금 생각을 해볼게요. 적절한 크기를 설정했다면, 토막들을 합쳐가면서 적절한 크기보다 커졌을 때, 그 이전 토막까지 잘라내면 한토막이 완성됩니다. 이렇게 하지 않으면 토막횟수가 무조건 크게끔 나타납니다.
게다가, 적절크기의 가장 작은 자르는 위치를 출력해야합니다. 이를 위해서 토막들의 뒤부터 확인하면서 횟수를 모두 사용하였다면 total에 그 조각의 토막시작점이 저장됩니다. 그렇지 않은 경우에는 무조건 맨 앞조각의 뒷부분이겠죠?
import sys
input = sys.stdin.readline
l, k, c = map(int, input().split())
position = sorted(list(set([0, *list(map(int, input().split())), l])))
# 나무토막들
pieces = [position[i] - position[i-1] for i in range(1, len(position))]
start = 1
end = l
while start <= end:
mid = (start + end) // 2
# 애초에 자를 수 없으면 크기를 키움
if max(pieces) > mid:
start = mid + 1
else:
total = 0
cnt = 0
# 토막들의 뒤부터 확인
for p in pieces[::-1]:
total += p
if total > mid:
total = p
cnt += 1
if cnt > c:
start = mid + 1
else:
# 적절한 크기
ans_result = mid
# 최대횟수를 모두 사용하면 total,
# 그렇지 않다면 맨 앞토막의 끝
ans_front = total if cnt == c else pieces[0]
end = mid - 1
print(ans_result, ans_front)
+
이 문제는 지금까지 풀었던 문제들중에서 긴 고민을 하고 많은 시도를 해보았습니다. 처음에는 단순한 문제라고 생각하였으나, 예외경우도 많았고 특히나 토막을 처음 치는 위치가 정말 생각하기 힘들더라구요.
