나무 자르기

• 파라메트릭 서치으로 푸는 방법과 그냥 정렬로 푸는 방법이 있다.
• 떠오르기 쉬운 것은 파라메트릭 서치이다. 단계별로 풀어보기의 이분탐색 부분에 있는 문제이기도 하고, 문제 분류에도 이분 탐색으로만 되어 있다. 결정 문제는 '절단기의 높이가 주어졌을때 M미터의 이상의 나무를 가져갈수 있는가?'가 된다. 집에 가져갈수 있는 나무의 길이를 O(n)에 쉽게 계산 가능하므로 당연히 이 결정문제도 O(n)에 풀린다. 절단기의 최대 높이를 [0, n] 사이에서 이분탐색으로 찾으면 된다 (k=가장 긴 나무의 높이). 시간 복잡도는 O(nlogk).
  • 그러나 이 풀이는 파이썬 기준으로 시간이 아슬아슬하다.. n≤1,000,000이고 k≤1,000,000,000 이니까 O(nlogk) 알고리즘이 통과되어야 할거 같은데.. 상수항을 얼마나 최적화하느냐에 따라서 통과 여부가 갈린다.
    • 예를 들면, '절단기의 높이가 주어졌을때 M미터의 이상의 나무를 가져갈수 있는가' 를 계산하는 부분을, 가져갈수 있는 총 길이를 계산한 다음에 비교하면 항상 n개의 나무에 대해서 모두 비교해야 하지만, 나무 한개씩 절단되는 길이를 더해나가다가 M이상이 되는 순간 True를 얼리 리턴하면 조금 더 빠르게 만들수 있다.
    • 조금 더 빠르게 하려면, 미리 tree들을 높이가 큰 순서대로 정렬을 시켜놓으면, 앞에서부터 처리하다가 절단기의 높이보다 더 짧은 나무가 나오면 그 이하는 계산을 안해도 된다. 내 경우는 여기까지 처리하니까 통과가 되었다.
    • 다른 사람의 빠른 코드들을 읽어보니, 크기가 같은 tree들을 묶어서 (counter을 이용해서) 처리하는 방식으로 가장 큰 속도 향상을 얻었다
• 굳이 이분탐색을 쓰지 않고도 바로 구할수도 있다. 나무들을 높이가 높은 순서대로 정렬해서, 그 높이들을 tree[0:n]이라고 하자. 절단기의 높이가 tree[i]에 있을 때의 절단된 나무의 총 길이를 cut[i] 라고 하자. 절단기를 tree[i]에서 tree[i+1]만큼 내리면, {내린 길이}*{높이가 tree[i]이상인 나무의 갯수} 만큼 총 절단된 길이가 늘어난다. 즉 cut[i+1] = cut[i] + (tree[i + 1] - tree[i]) * (i + 1)이 성립된다. 이제 cut[x]를 순서대로 계산하다가 cut[x] < M < cut[x+1] 인 x를 찾으면, 최종 답은 tree[x]에 (M - cut[x]) 를 x로 나눈 값을 더해서 구할수 있다.
  • 이 방식으로 풀면 정렬에 O(nlogn), cut값을 계산하는 데에 O(n). 총 O(nlogn)이 걸리고, 파이썬으로도 여유있게 통과된다.
  • 여기에서도 높이가 같은 tree들을 (높이, 갯수) 쌍으로 묶어서 저장한후 처리하면 속도가 더 빨라진다.

"""Solution code for "BOJ 2805. 나무 자르기".

- Problem link: https://www.acmicpc.net/problem/2805
- Solution link: http://www.teferi.net/ps/problems/boj/2805
"""

from teflib import algorithm


def main():
    def is_less_than_m(height):
        total = 0
        for t in trees:
            if t <= height:
                return True
            total += t - height
            if total >= M:
                return False
        return True

    N, M = [int(x) for x in input().split()]
    trees = [int(x) for x in input().split()]

    trees.sort(reverse=True)
    answer = algorithm.binary_search(0, max(trees) + 2, is_less_than_m) - 1

    print(answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 2805. 나무 자르기".

- Problem link: https://www.acmicpc.net/problem/2805
- Solution link: http://www.teferi.net/ps/problems/boj/2805
"""


def main():
    N, M = [int(x) for x in input().split()]
    trees = [int(x) for x in input().split()]

    trees.sort(reverse=True)
    trees.append(0)
    total_cut = 0
    for i in range(1, N + 1):
        total_cut += (trees[i - 1] - trees[i]) * i
        if total_cut >= M:
            answer = trees[i] + (total_cut - M) // i
            break

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.algorithm.binary_search