💡문제 분석 요약

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

• 절단기의 높이인 H로 나무를 잘라 필요한 만큼만 집으로 가져가려 한다.
• 적어도 M미터의 나무를 집에 가져가기 위해 절단기 높이의 최댓값을 구하여라

💡 나무의 수 = 4, 집으로 가져가려 하는 나무 길이 = 7
나무 리스트 = [ 20, 15, 10, 17 ]

m = 15일 때 나무의 길이 2 + 5 = 7

따라서 m = 15

💡알고리즘 설계

• start = 0, end = max(tree)
• start와 end가 같아져 이분탐색이 끝날 때까지 while loop
• mid를 start와 end의 중간으로 두고, 모든 값에서 mid를 빼 총 나무 길이 확인
  • 잘린 나무가 목표치 이상이면 mid+1을 start로 두고 다시 while문 반복
  • 잘린 나무가 목표치 미만이면 mid-1을 end로 두고 다시 while문 반복

💡코드

import sys

def cuttree(need, tree) :
    start = 1
    end = max(tree)
    while start <= end :
        mid = (start + end) // 2
        s = 0
        for i in tree :
            if i >= mid :
                s += i - mid
        if s >= need : start = mid + 1
        else : end = mid - 1
    print(start)

n, need = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))

cuttree(need, tree)

💡시간복잡도

• tree의 최댓값을 N이라고 한다면 1부터 N까지 이진탐색하므로 O(logN)
• 위 loop 안에서 tree의 길이(M)만큼 for loop를 돌기 때문에 O(M)
• 따라서 시간복잡도는 O(MlogN)

💡 틀린 이유

• 4 10 [4 5 6 7]을 입력했을 때 기대값 3 대신 4 출력
• 시간초과

💡 틀린 부분 수정 / 다른 풀이

• start와 end를 설정할 때 (start + end) // 2 연산을 수행하므로, 가운데 값을 구하는 것이 아니라 더 작은 값인 start를 사용하여 연산을 진행한다. 따라서 end를 결과값으로 출력해야하는데 start를 출력하도록 해서 이를 수정했다.

import sys

def cuttree(need, tree) :
    start = 1
    end = max(tree)
    while start <= end :
        mid = (start + end) // 2
        s = 0
        for i in tree :
            if i > mid :
                s += i - mid
        if s >= need : start = mid + 1
        elif s < need : end = mid - 1
    print(end)

n, need = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))

cuttree(need, tree)

💡 느낀점 / 기억할정보

• 이진탐색 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘
  
• 주어진 테스트케이스 뿐만 아니라 다양한 반례를 생각해보고 디버깅해 정확도를 높일 수 있도록 하자