백준 2805번 나무 자르기

이분탐색문제다

태그보고나서야 알았다.

 

이분탐색은 정렬배울때 이후로는 사실 처음본거라 개념정리부터 다시하고 풀었다.

 

import sys
n,m=map(int,sys.stdin.readline().rstrip().split())
arr=list(map(int,sys.stdin.readline().rstrip().split()))
def calc_w(h):
    result=0
    for i in range(n):
        if arr[i]-h<=0:
            continue
        result+=(arr[i]-h)
    return result

def calc_max_h(s,e):
    w=calc_w((s+e)//2)
    if w==m:
        print((s+e)//2)
        return
    elif w>m:
        calc_max_h((s+e)//2,e)
    else:
        calc_max_h(s,(s+e)//2)
calc_max_h(0,1000000)

w>m부분이 좀 헷갈렸는데 생각해보면 당연한게 s가 커지면 w가 줄어들고 e가 줄어들면 w가 커진다.

이게 왜 시간초과지

 

아 m과 w가 같을때만 종료되서 그렇다.

s와e가 같을때도 종료시켜줘야한다.

헷갈리니까 그냥 반복문으로 수정하자

 

import sys
n,m=map(int,sys.stdin.readline().rstrip().split())
arr=list(map(int,sys.stdin.readline().rstrip().split()))
right=0
left=0
for i in arr:
    right=max(right,i)
def calc_w(h):
    result=0
    for i in range(n):
        if arr[i]-h<=0:
            continue
        result+=(arr[i]-h)
    return result

while right>=left:
    mid=(right+left)//2
    w=calc_w(mid)
    if w>=m:
        left=mid+1
    else:
        right=mid-1
print(right)

이렇게 수정했다.