문제요약

시간 제한: 1 초 문제

본문 요약:
절단기에 높이 H를 지정한다. 높이를 지정하면 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다.
필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력:
첫째 줄에 나무의 수 N과 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력:
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

---

풀이

이전에 업로드했던 랜선자르기 문제와 거의 유사한 문제이다.
이진 탐색으로 문제를 풀어야하며 이때 유의할 점은 자를 수 있는 높이 중 가장 높은 높이를 구해야한다는 점과 자를 나무의 높이가 M과 정확히 일치하지 않을 수 있다는 점이다.

이 두가지를 생각하여 있을 수 있는 반례를 처리하여 구해야 한다.

이진 탐색의 첫 범위는 1부터 시작하며, 마지막 범위는 리스트의 가장 큰 값부터 시작한다.
mid는 당연히 이 둘의 중간값이다.
기존 이진 탐색과는 다르게 start와 end의 값 조정은 sum을 기준으로 이루어진다.
sum은 현재 리스트의 각 요소에서 mid를 뺀 값이다.
단, 절단기의 높이보다 낮게 있는 나무들은 잘리지 않으므로 mid보다 작은 값은 0이 된다.
마지막으로 탈출 조건을 sum == m 으로 두거나 start < end로 두면 안된다.

코드:

n, m  =  map(int, input().split())
t = list(map(int, input().split()))
start = 1
end  = max(t)
while start <= end:
    mid = (start + end) // 2
    sum = 0
    for tree in t:
        sum += max(tree - mid, 0)
    if sum >= m:
        start = mid + 1
    else:
        end = mid - 1
print(end)

---

가능한 실수

1. sum == m일 때 탈출 후 end 프린트

    if sum >= m:
        start = mid + 1
    else:
        end = mid - 1
print(end)

이 부분을

    if sum == m:
        break
    elif sum > m: 
        start = mid + 1
    else:
        end = mid - 1
 print(end)

이렇게 sum이 m과 같을 때 탈출하고 end를 출력할 경우 다음과 같은 반례가 발생한다.

반례:

6 35
17 93 7 47 53 25

ans : 58, wrong ans : 69 

이 경우 모든 리스트에서 mid를 뺀 후 더한 값이 m과 같아서 탈출하였다.
때문에 mid를 출력할 경우 정상적인 답이 나오겠지만 아직 end는 답에 멀찍이 떨어져 있기 때문에 오답이 되어 버리는 것이다.
즉, start와 end는 답과 멀리 떨어져있지만, 우연히 mid가 답과 일치하여 답을 찾아버렸는데 이때 end를 출력해버리니 반례가 생겨버리는 것이다.
그러면 sum == m일 때 출력하고 mid를 프린트해버리면 어떨까?

2. sum == m일 때 탈출 후 mid 프린트

동일한 부분을

    if sum == m:
        break
    elif sum > m: 
        start = mid + 1
    else:
        end = mid - 1
 print(mid)

이렇게 수정하고 같은 조건에서 mid를 출력하는 경우 다음과 같은 반례가 발생한다.

반례:

5 90
44 46 4 92 61

ans: 38, wrong ans: 39

이 경우 이진탐색을 계속 진행하면 마지막 이전 부분에서 start가 38, end가 39가 되고 이때 mid는 38이 되며 sum은 91이 된다.

마지막 바로 이전:
start: 38, end: 39, mid: 38 sum: 91

그리고 sum은 m보다 크기 때문에 start는 39가 되며 mid도 39가 된다.
이때, sum은 87이 되어버리고 오답을 출력해버린다.

마지막:
start: 39, end: 39, mid: 39, sum: 87

즉, 정답이 정확하게 m이 아닌 경우가 있고, 이런 경우 start나 end가 한 칸 더 이동을 해버리기 때문에 오답을 출력해버리는 것이다.
따라서 이런 경우는 end가 탈출 후 -1이 되기 때문에 end를 출력해야만 한다.

하지만 end를 출력해버리면 위에서 봤듯이 반례가 발생해버린다. 따라서 sum == m일 때 탈출하면 안되는 것이다.

3. while문을 start < end일 때 탈출

이 경우도 반례가 발생한다.
이 경우는 쉽게 생각할 수 있기 때문에 따로 적지는 않겠다.