[BOJ] 백준 2805번 - 나무 자르기 (Python)

문제

문제 바로가기

해결

이진 탐색 알고리즘 문제인 것을 알고 풀기 시작했다.

또한 조건을 만족하는 가장 알맞은 값을 찾는 최적화 문제, 즉 파라메트릭 탐색문제이므로 결과값에 따라 이진 탐색처럼 시작값, 종료값을 조정해주면서 문제를 풀어나갔다.

첫 번째 제출

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
trees = list(map(int, input().split()))

start = 0
end = max(trees)

while True:
  sum = 0
  mid = (start + end) // 2

  for t in trees:
    if t - mid > 0:
      sum += t - mid

  if sum == M:
    break
  elif sum > M:
    start = mid + 1
  else:
    end = mid - 1

print(mid)

예제에 따른 출력 결과는 정확했지만..

시간 초과다.. 가장 간결하게 작성했다고 생각했지만 무언가 잘못된 부분이 있는 것 같다..

두 번째 제출 (정답)

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
trees = list(map(int, input().split()))

start = 0
end = max(trees)

while (start <= end):
  sum = 0
  mid = (start + end) // 2

  for t in trees:
    if t > mid:
      sum += t - mid

  if sum < M:
    end = mid - 1
  else:
    result = mid
    start = mid + 1

print(result)

예제와 함께 살펴보자.

처음에는 절단기의 높이의 범위를 0 ~ 20(가장 긴 나무의 길이)으로 설정했고, 중간값은 그 중간값인 10이었다.

0으로 설정할 경우, 모든 나무를 다 자르기에 최대값이고, 20으로 설정할 경우 얻는 나무의 길이는 0이므로 최소값이다.

즉 절단기의 높이를 조절해가면서 나온 결과값에 따라 절단기의 높이를 이진 탐색해주면 되는 것이다.

디버깅

시도	변수
첫 번째 시도	mid : 10 / sum : 22 > M : 7 / result : 10 / start : 11, end : 20
두 번째 시도 (정답)	mid : 15 / sum : 7 == M : 7 / result : 15 / start : 16, end : 20
세 번째 시도	mid : 18 / sum : 2 < M : 7 / result : 15 / start : 16, end : 17
네 번째 시도	mid : 16 / sum : 5 < M : 7 / result : 15 / start : 16, end : 15

sum이 M보다 작을 경우는 더 많이 잘라야 하기 때문에 end가 mid - 1로 내려오면서 mid가 더 내려와 더 많은 나무를 자를 수 있게 된다.

이렇게 더 많은 나무를 자르다가, sum이 M보다 많아질 경우가 되면 이제 덜어내야 하는데, 덜어내기 위해서는 mid가 더 올라와야 하므로 start가 mid + 1만큼 올라온다.

결국은 M미터보다 sum이 커지는 순간이 최소 M미터의 나무를 집에 가져가기 위해 설정할 수 있는 높이의 최댓값이 된다.

이런 반복 구조를 실행하다가 보면 언젠가 end와 start가 서로 가까워지면서 결국 start가 end를 넘어서는 순간이 오는데 그 때가 while 반복문이 종료되는 시점이다.

References

이것이 취업을 위한 코딩테스트다 with 파이썬