[백준] 2805번 : 나무 자르기

저번 코테에서 이분 탐색 문제에서 개박살이 나서 이분탐색을 집중적으로 공부해야겠다는 생각이 들어 준비했다.

 

 

 

 

 

 

 

 

접근법

- 기존에 이분 탐색 문제들을 쭉 훑어보다 보니 비슷한 결을 찾을 수가 있었다. 대체로 범위가 굉장히 크고(완전 탐색을 하면 시간 초과가 발생하게 하려고) 원하는 값을 찾기 위해서 범위를 좁혀나가는 방법을 채택하게 한다.

 

- 이 문제도 나무의 길이가 2,000,000,000으로 엄청 커서 완전 탐색으로 찾으면 시간초과가 발생한다. 그래서 이분탐색으로 start를 0, end를 2,000,000,000으로 설정한 후 mid = (start + end) // 2로 설정해가면서 반씩 줄여나가는 방법을 채택했다.

 

- while문으로 start <= end 조건을 설정하고, 내부에서 mid를 위에서 말한 것 처럼 설정한다. 그 후 for문을 돌면서 tree배열의 값이 mid보다 클 경우(자르는 위치보다 나무가 길 경우, 이 경우에만 나무의 윗동이 잘리니까) count에 잘린 값 즉, i - mid의 값을 더해주면서 계산한다.

 

- for문을 다 돈 후 count의 값이 M의 값보다 같거나 크면 주어진 조건을 만족하기 때문에 더 높은 곳에서 만족하는 값이 있는지 찾기 위해 범위를 좁힌다. mid의 값까지는 만족을 하기 때문에 start를 mid + 1로 설정한 후 같은 로직을 반복한다.

 

- 반면에 count < M인 경우 주어진 조건을 만족하지 못했기 때문에 나무를 자르는 위치를 아래로 낮춰야한다. 범위를 좁히기 위해서 mid까지는 조건을 만족시키지 못했으므로 end를 mid - 1로 설정하고 로직을 반복한다.

 

- 이렇게 수행한 결과 정답은 맞췄지만 시간초과가 발생했다. 곰곰히 생각해본 결과 for문의 안에서 배열의 크기가 엄청 크다면 그로 인한 시간초과가 발생했겠다는 생각이 들었다. 그래서 for문을 도는 와중에 count의 값이 이미 M보다 크다면 더 for문을 돌 필요가 없으므로 start = mid + 1로 설정하고 for문을 빠져나가는 로직을 추가해주었다.

 

 

 

 

 

 

 

풀이

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
    
tree = list(map(int, input().split()))

start = 0
end = 2000000000

while start <= end :
    mid = (start + end) // 2
    count = 0

    for i in tree :
        if i > mid :
            count += i - mid
        if count >= M :
            start = mid + 1
            break

    if count >= M :
        start = mid + 1
    else :
        end = mid - 1
print(end)    

 

 

 

 

 

 

 

결과