[백준 2805 파이썬] 나무 자르기 (실버3, 이분 탐색)

알고리즘 유형 : 이분 탐색
풀이 참고 없이 스스로 풀었나요? : O

https://www.acmicpc.net/problem/2805

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
trees = [*map(int, input().split())]

def cutting(cutter):
    length = 0
    for tree in trees:
        rest = tree - cutter
        if rest > 0:
            length += rest
    return length

def findCutter(start, end, aim):
    if start > end:
        return end
    
    mid = (start + end) // 2
    if cutting(mid) >= aim:
        return findCutter(mid+1, end, aim)
    else:
        return findCutter(start, mid-1, aim)

print(findCutter(1, max(trees), M))

풀이 요약

1. 1654 랜선 자르기 문제랑 풀이가 거의 동일하다. 차이점은 이분 탐색 과정에서 mid 값으로 어떤 값을 만들어서 조건문을 걸지가 조금 다르다.

2. 1부터 나무들 중 가장 높은 수까지를 탐색 범위로 잡고 이분 탐색한다.

3. mid가 아닌, cutting(mid) 값으로 조건문을 건다. cutting 함수는, 입력값 cutter에 대해, 모든 나무의 높이에서 cutter만큼을 빼고, 그 값이 0 이상(cutter로 나무를 한 번 이상 자를 수 있고, 잘랐을 때 남은 나무 길이가 0 이상인 경우를 의미함)일 때 남은 나무 길이의 총 합을 리턴해주는 함수이다.

4. 이 값을 가지고 조건문을 건다. 이 값이 원하는 나무 총 길이 M보다 크면, cutter(=mid) 높이가 좀 낮아서 너무 많이 남겼다는 뜻이므로, cutter 높이를 높여줘야하므로 start = mid+1로 재귀 호출. 그 반대의 경우에는 마찬가지 원리로 end = mid-1로 재귀 호출.

5. 여기서, cutting(mid) 값이 M과 같은 경우에도, cutter의 높이를 높이는 경우, 즉 start = mid+1로 재귀를 뻗어나가줘야한다.

   남는 나무 길이의 총합이 M임을 만족하는 cutter의 높이가 여러개인 경우를 생각해보면, 이 때 이분 탐색으로 찾은 cutter(=mid)를, 높이를 점점 높혀가면서 조건을 만족하는 cutter의 최대인 경우까지 계속 진행해나가야한다.

   start는 최대cutter 다음 인덱스에 멈추고, end는 최대cutter, 즉 M이 되도록 하는 cutter 중 최대에 멈추고, 이 때의 end를 반환하면 답이다.

배운 점, 어려웠던 점

• 1654 랜선 자르기 문제와 거의 유사한 풀이였어서 어렵지 않았다.