백준 2805
반복문을 사용해 이진탐색의 방법으로 문제를 풀었다. 이진탐색은 반씩 쪼개어 탐색을 하므로 순차탐색보다 훨씬 시간을 줄일 수 있다. 그런데 시간초과가 너무 많이 나서 결국 python3가 아닌 pypy3로 제출하여 통과되었던 문제이다. pypy3가 더 빠르게 수행된다고 알고있다.
방법1. 반복문으로 이진탐색 구현하기
n, h = map(int, input().split())
# 한 줄에 여러개 받기
tree = list(map(int, input().split()))
# 자를 수 있는 나무 길이의 범위
start = 0
end = max(tree)
while(start <= end):
mid = (start + end)//2 #이진탐색을 위해 반으로 쪼개기
sum = 0
for ele in tree:
if ele > mid :
sum += ele-mid #그때그때 mid길이만큼 나무를 잘라 남은 길이의 합을 구하기
if sum >= h: #최소 h만큼은 잘라야하기 때문에 합이 h보다 크거나 같으면
max_h = mid #그때의 mid를 기억해준다.(반복문은 조건이 맞는 동안 계속 돌것이므로 알아서 최종 mid의 최댓값이 저장)
start = mid + 1 #sum이 너무 크면 더 많이 잘라야하기때문에 자를 수 있는 최소 길이를 높여준다.
elif sum < h: #sum이 너무 작으면 너무 많이 자른것이므로 자를 수 있는 최대 길이를 낮춰준다.
end = mid - 1
print(max_h) #최대로 자를 수 있는 길이를 출력한다.이진 탐색
반으로 쪼개면서 탐색하기. 매 스텝마다 탐색의 범위를 절반씩 줄여나가며 정답으로 가까워지는 탐색 방법으로 탐색 방법 중 매우 빠른 속도를 자랑하는 알고리즘이다. 내부의 데이터가 정렬되어있어야 사용이 가능하고, 시작, 중간, 끝 이렇게 세개의 변수를 사용한다.
이진탐색의 개념을 공부하면서 이 문제를 이해했는데,
https://nerogarret.tistory.com/58 여기에 이진탐색과 관련해서 문제해설이 아주 잘 되어있다.
