코딩하는 해맑은 거북이

[Python] 나무 자르기 - 백준 (이진탐색) 본문

코딩테스트

[Python] 나무 자르기 - 백준 (이진탐색)

#CJE 2023. 1. 25.
해당 글은 백준 2805번 문제 '나무 자르기'를 다룬다.

문제

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

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

 

설명

해당 문제는 나무의 길이가 1부터 20억까지의 정수이므로 이를 완전탐색하기엔 시간이 너무 오래 걸린다.

그래서 너무 큰 수를 보면 이진탐색으로 풀어야 시간을 O(logN)으로 줄일 수 있다.

그리고 while문 안에 for문은 sum1이 m이상이 되면 break를 해주어야 시간초과되지 않을 수 있다.

 

코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
tree = list(map(int, input().split()))

start = 0
end = max(tree)
result = 0
while start <= end:
    mid = (start+end)//2
    sum1 = 0
    for i in range(n):
        if tree[i] > mid:
            sum1 += (tree[i]-mid)
            if sum1 >= m:
                break
    if sum1 >= m:
        result = mid
        start = mid+1
    else:
        end = mid-1

print(result)

     

 

 

Comments