212. 나무자르기

1) 어떤 전략(알고리즘)으로 해결?

• 이분탐색

2) 코딩 설명

<내 풀이>

<내 틀렸던 풀이, 문제점>

시간초과 나는 풀이

import sys
n, m = map(int, sys.stdin.readline().rstrip().split())
trees = list(map(int, sys.stdin.readline().rstrip().split()))

longest = max(trees)

for i in range(longest, -1, -1) :
    chk=0
    for tr in trees :
        summ = tr-i
        if summ > 0 :
            chk+=summ
    if chk==m : 
        print(i); exit()

       

• 이걸 이분탐색으로 어케 적용?

이분탐색으로 바꿨지만 4 % 때 틀리대

import sys
n, m = map(int, sys.stdin.readline().rstrip().split())
trees = list(map(int, sys.stdin.readline().rstrip().split()))
trees.sort()

longest = max(trees)

l=0; r = longest-1
while l<=r : 

    mid=(l+r)//2
    res=0

    for tr in trees :
        if tr-mid> 0 : res+=tr-mid
    
    if res ==m : 
        print(mid); exit()

    elif res > m :
        l=mid+1

    else : 
        r = mid-1

=> 항상 m이랑 똑같은 총합을 찾는게 아니라 적어도 m이다!

<반성 점>

<배운 점>

배열을 돌리지말고 내가 찾고자 하는 대상 후보들을 (최저값부터 최댓값까지) l, r로 설정해놓고 검사!