코딩하는 해맑은 거북이
[Python] 나무 자르기 - 백준 (이진탐색) 본문
해당 글은 백준 2805번 문제 '나무 자르기'를 다룬다.
문제
https://www.acmicpc.net/problem/2805
설명
해당 문제는 나무의 길이가 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)
'코딩테스트' 카테고리의 다른 글
[Python] 시소 짝꿍 - 프로그래머스 (0) | 2023.02.13 |
---|---|
[Python] 숫자 변환하기 - 프로그래머스 (DP) (0) | 2023.02.07 |
[Python] 회의실 배정 - 백준 (그리디) (0) | 2023.01.25 |
[Python] 평범한 배낭 - 백준 (DP) (0) | 2023.01.25 |
[Python] 강의실 배정 - 백준 (그리디) (0) | 2023.01.25 |
Comments