실버 II

💡문제 분석 요약

binary search 이진탐색

💡알고리즘 설계

절단기 범위를 start,end로 설정한다.

이진 탐색으로 해당 길이의 절단기로 잘랐을 때 모을 수 있는 나무를 cut에 넣고, 만약 cut이 크면 범위를 줄여줘야 하므로 end = mid -1로 설정한다.

여기서 절단기의 최댓값을 알아야 하므로 return end값을 해야한다. 이때 값이 end에 담겨서 최종 반환되므로, cut==m인 경우 while문은 start가 end보다 커야 끝나므로 start의 범위를 위로 올려서 다시 while에 돌려야 한다. 즉 start를 최대한 높여야 끝난다.

반대로 start를 반환하는 최솟값을 구하는 경우, start가 end 보다 커야 끝나므로 cut≤m일때 end의 값을 최대한으로 내려야 끝난다. 즉 start를 리턴해야되므로 start는 건드리지 않고 end를 조정해서 끝내야한다.

💡코드

import sys
input = sys.stdin.readline
n,m = map(int,input().strip().split())
trees = list(map(int,input().strip().split()))
#binary search

start,end = 1,max(trees)
while start<=end :
    cut= 0
    mid = (start+end)//2
    for tree in trees: 
        if tree>mid:
            cut += tree-mid
    if cut<m: #더 잘라야 하므로 절단기를 낮춰야 함.
        end = mid -1
    else:
        start= mid +1
print(end)

💡틀린 이유

일단, start의 값을 1로 잡지 않고 tree의 최솟값으로 잡은 것이 화근이었다. 애초부터 출력값은 0도 될 수 있고 최댓값만 확정 된 것인데 (나무 보다 더 긴 절단기로 자를 수 없기에) 최솟값을 마음대로 정해버렸다.

💡시간복잡도

n log n

💡 기억할정보

범위 중 최댓값을 반환해야하는 경우, mid==비교값이 되는 경우에 최솟값을 변경하고, 최솟값을 변환하는 경우에는 최댓값을 변경해줘야 한다. 왜냐하면 while문의 탈출 조건이 start>end이기 때문이다.