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

아이디어

이진탐색으로 접근해야 했지만 일단 가장 먼저 떠올랐던 생각은 부등식을 세워 최댓값(정수)을 구하는 방법이었다.
어떻게 이진탐색을 활용해야 할지가 고민이었는데 구매했던 도서의 예제 문제에서 답을 찾을 수 있었다.

중요 포인트 (책 내용 발췌)
1) 이러한 문제의 유형은 parametric search 유형의 문제이며 이는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용한다. 즉, 적절한 높이를 찾을 때까지 높이 H를 반복해서 조정하는 것이다.
2) 이진탐색 범위를 축소시켜야 한다. 아무리 순차탐색이 아닌 이진탐색으로 진행한다고 하여도 전체 범위로 탐색을 진행시키면 시간초과가 발생할 수 있다.
-> 절단기의 높이는 가장 길이가 긴 나무의 길이 이하일 경우에 자를 수 있다.
따라서, 문제의 예시로 생각해보면 시작점은 0으로 두고 끝점은 가장 긴 나무의 길이로 두어야 한다.

1차 시도

# 나무 자르기
import sys

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

start = 0
end = max(tree)

while(start <= end):
    check = 0
    mid = (start + end) // 2
    for t in tree:
        if t - mid > 0:
            check += (t - mid)
    if check == M: #
        break
    elif check > M: # 가져갈 나무의 길이보다 많이 가져가게 되는 경우 -> 오른쪽 부분 탐색
        start = mid + 1
    else: # 왼쪽 부분 탐색
        end = mid - 1

print(mid)

예제는 다 맞았느나 10%에서 '틀렸습니다'가 떴다.
적어도 M미터 이상이라는 조건을 간과했다. 무조건 동일한 값이여야 하는 것이 아니라 최소한 M미터 이상의 나무는 가져가야 한다.
반례)
6 12
19 9 18 20 17 8
정답 - 15
내 답변 - 16
-> 16을 기준으로 생각해보면 10밖에 챙기지 못하기 때문에 적어도 12미터 이상이라는 조건에 부합하지 않는다.

2차 시도

책 예제코드 이해 후 재작성 - 코드는 동일한듯...

# 나무 자르기
import sys

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

start = 0
end = max(tree)

result = 0
while(start <= end):
    check = 0
    mid = (start + end) // 2
    for t in tree:
        if t - mid > 0:
            check += (t - mid)
    if check < M: # 왼쪽 부분 탐색
        end = mid - 1
    else: # 오른쪽 부분 탐색
        result = mid
        start = mid + 1

print(result)

조건문의 등호도 왼쪽 탐색이 아니라 오른쪽 탐색인 경우에 해당되도록 바꿔줬다.
"적어도" H미터 이상이라는 조건을 만족시켜줘야 하기 때문이다.
=> sys,이진탐색을 사용했음에도 시간초과가 떠서 pypy3로 제출했다.