[백준][이진탐색] 2805 - 나무 자르기

문제

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

2805번: 나무 자르기

이코테의 떡볶이 떡 만들기 문제와 동일하다.

 

구현

이진 탐색에 대해서는 숫자로 이루어진 배열 안에서 특정 숫자가 존재하는지 찾는거에 대해서만 배운 상태였어서

이진 탐색을 활용해 어떻게 푸는지도 감을 잡지 못했는데

 

파라메트릭 서치 알고리즘으로 풀면 된다는 해설을 보면서 점점 이해가 됐던 것 같다.

파라메트릭 서치로 문제를 바라보면 다음과 같다. 

 

• 최적화
  N개의 나무들을 몇의 높이(h)에서 잘라야 M 만큼의 나무길이를 얻을까
• 결정
  h에서 N개의 나무들을 자르면 M 만큼의 나무들이 나오는가?
  
  

h-> mid로 세팅하고 잘랐을 때 자르고 나온 total이

• M 보다 작다면 h를 더 내려야 함
  if total < M
• M 보다 크다면 h를 더 올려야 함
  if total > M
  하지만 M 보다 크다면 길이 M을 만족하기도 한다는 뜻으로 
  if total >= M이 되야 한다.

여기서 하나 짚고 넘어가야할게, h를 더 내린다는 말은 mid를 더 내린다는 말이 되며

mid를 내린다는 것은 (start + end) // 2가 내려가야 한다는 뜻이니

start는 그대로 있고 end 값이 낮아져야 한다는 게 된다.

즉, end = mid - 1이 되면 되는 것

 

반대의 경우에도 마찬가지로 생각

 

이에 따라 코드를 작성하면 다음과 같다.

 

코드

import sys
input = sys.stdin.readline

def solution(trees, target, start, end):
  result = 0
  while start <= end:
    mid = (start + end) // 2
    total = 0
    for tree in trees:
      if mid < tree:
        total += tree - mid
    if total < target:
      end = mid - 1
    else:
      result = mid
      start = mid + 1
  return result

N, M = map(int, input().split())
trees = list(map(int, input().split()))
print(solution(trees, M, 0, max(trees)))

이진 탐색을 사용한다는 것은 입력 데이터가 많거나 탐색 범위가 매우 넓은 상황이기 때문이니

평소처럼 input()을 사용하는 것 보다 sys를 사용하는 것이 더 효율적이다. 

 

나 같은 경우는 평소처럼 input을 그대로 쓰면서 맨 위에서 

import sys
input = sys.stdin.readline

위 코드를 통해 input이 sys.stdin.readline 함수를 뜻하게끔 바꿔놨다.