3 4

3 3 5

import sys
from collections import deque
input=sys.stdin.readline
array=deque()

N,M = map(int,input().split())

array = list(map(int,input().split()))
start,end = 0,1000000000
while start<=end:
    mid = (start+end)//2
    S=0
    print("start {} mid {} end {} ".format(start,mid,end))
    for i in array:
        if i>mid:
            S+=i-mid
    if  S>=M:
        start = mid+1
    else:
        end = mid-1
print(end)

결국 이렇게 구성하여 풀게되었습니다.

3 4

3 5 5 를 입력하게되면 start mid end 기준으로 (0 2 5) -> (3 4 5) -> (3 3 3) 순으로 루프를 돌면서 결국 S==M구문을 통해서 mid값인 3이 출력되었습니다.

분명 S를 기준으로 조건문을 걸면서 하고있는데 허점이 생기는걸까요????

저는 조건을 다시 짜기 시작했습니다. S(나무를 자르고 얻은 자른나무의 길이의합) > M ( 나무를 잘라서 얻어야하는 최소조건) 보다 클 경우 start=mid+1 을하고

S<M 의 경우 end=mid-1의 조건을 거는것은 맞는것같습니다, 2진탐색을 하는 필수조건이기떄문입니다.여기서는 S==M가 print(mid) 을 살펴봐야 할것같았습니다. S==M 일때에 print(mid)로 출력하면 위에 있는 반례를 통과하지못합니다.

제 코드는 start<=end 의 조건을 만족하는 경우에 반복문을 시행합니다. 이 경우 만일 S==M이라는 조건을 가지고 있지 않더라도 start와 end는 결국 원하는 답에 근접하게 될것입니다. 맞그렇다면 조건문을 거치고 거쳐서 start와 end가 mid와 1의 차이만큼 날떄에 ex) (start=3 mid=4 end=5) S<M의 조건을 만족하여 end가 mid-1이 되고 (3 3 3) 으로 된뒤 start와 end가 아직 3 3 으로 같으므로 반복문을 한번더 돌고 S<M의 조건을 만족하여 end값이 mid-1로 변경하여 end=2 인상태로 반복문이 종료됩니다.

솔직하게 현상만으로 문제를 풀게되었는데, 아직까지 확실하게 감이안오네요 2진탐색 문제에 대해 익숙하지않아서 2진탐색을 사용해야 하는문제일것같다는 느낌은 드는데 실제 활용부분에서 어려움이 많습니다. 제가 풀어서 낸 답에 S>=M 또한 S==M 구문의 조건이 마땅히 떠오르지않아서 하다보니 조건이 얼추맞은거라 완벽히 이해해서 문제를 풀었다고 보기는 어려울것같습니다.

반례 제공해주셔서 감사합니다

wnwoghd22님