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

난이도 : Silver 2
Link : https://www.acmicpc.net/problem/2805
Tag : 이분탐색, 매개 변수 탐색
풀이일자 : 2024년 9월 23일

📌 문제 탐색하기

N : 나무의 개수
M : 가져갈 나무의 길이
tree : 나무의 높이

가능한 시간복잡도

N의 크기는 1,000,000 이며 M의 크기는 2,000,000,000 이므로
나무의 개수대로 1부터 자를 수 있는 모든 조건을 계산하는 것은 시간복잡도상 문제가 발생한다.

따라서 이분탐색을 통해 자를 수 있는 조건을 탐색하는 횟수를 줄여야 한다.

📌 문제 접근 방법

이분탐색을 통해 자를 경우의 수를 구해야한다.
자를 높이인 시작점을 start
자를 높이의 마지막 점을 end로 만든다.
start와 mid의 중간지점을 자르는 높이라고 가정하고 이분 탐색을 시작한다.

주어진 문제에서 집에 필요한 나무를 딱 맞춰서 가져갈 필요는 없기 때문에 mid 범위에서 잘랐을때 설정된 높이가 큰 값을 answer로 저장하면 된다.

📌 코드 설계하기

1. N, M을 입력받는다.

2. tree를 입력받고 sort하여 정렬한다.

3. find_height 함수를 생성한다.

   • 이 함수에서 이분탐색이 진행된다.
   • start = 0 end = tree[-1] 로 지정한다.
   • start와 mid의 중간값을 mid로 설정한다.
   • mid로 설정된 절단기로 모든 나무들을 잘랐을때 값이 M보다 크거나 같다면 answer에 저장하고, start = mid + 1로 업데이트 한다.
   • mid로 설정된 값으로 잘랐을때 그 외 경우라면 end = mid -1로 업데이트한다.

4. answer를 출력한다.

📌 시도 회차 수정 사항

1. 틀렸습니다. (시간초과)

문제에서 적어도 M미터의 나무를 가져가기 위해서 설정한 높이를 구해야 하는데 높이를 딱 맞춰서 갈 수 있겠금 if문을 작성하여 딱 맞추는 경우가 불가능할때 무한 루프에 빠지는 모습을 볼 수 있었다.

📌 정답 코드

import sys
N,M = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))
tree = sorted(tree)

def find_height():
    start = 0
    end = tree[-1]
    while start <= end:
        tmp = 0
        mid = (start + end) // 2
        for i in range(N):
            if tree[i] - mid > 0:
                tmp += tree[i] - mid
        if tmp >= M:
            answer = mid
            start = mid + 1
        else:
            end = mid - 1
    return answer

print(find_height())