[파이썬] BOJ 2805번 - 나무 자르기

링크

2805번: 나무 자르기

문제

• 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

• 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다.

• 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자.

• 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

• 상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 넘기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

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

풀이

• N과 M의 범위를 보니까 선형 탐색으로 풀면 시간 초과가 뜰 것 같다. 이진 탐색으로 접근하자.

• 실제로 계산을 하는 과정에서 절단기 높이를 알아야 잘라진 나무 높이의 합을 구할 수 있으니, 절단기 높이를 조절하면서 '나무의 합이 나올 수 있는 전체 범위' 중에 내가 찾는 나무의 합을 찾아 나가는 방식을 취하자.

• 예시: 나무의 개수 = 4, 잘라진 나무의 합 = 7 / 각 나무 높이 = 20, 15, 10, 17

• 절단기는 0부터(잘라진 나무의 합 = 나무 전체 합) 가장 높은 나무 높이 -1 까지 될 수 있다.(잘라진 나무의 합 = 1)

  • 절단기 범위 : 0 ≤ x ≤ 19 / 잘라진 나무의 합 : 1 ≤ y ≤ 62

• 이제 절단기 범위 내에서 특정 높이를 구하면 원하는 잘라진 나무의 합을 구할 수 있다.

  • 이때 이진 탐색을 활용해야 한다. 이진 탐색은 중앙을 기준으로 범위를 쪼개고, 범위를 점점 좁혀 나가는 것이다.

• 0 ≤ x ≤ 19의 중간 값을 구하면 (0+19) // 2 = 9가 된다. 절단기 9가 얻는 나무의 합은 26.

• 필요한 나무의 합(7)은 26보다 작다. 범위를 좁혀야 한다.

  • 그러면 1 ≤ y < 26이 된다. 절단기의 범위는 9 ≤ x ≤ 19.

• 한번 더 절단기의 범위를 좁혀 보자. 중간 값은 (9+19) // 2 = 14. 절단기 14가 얻는 나무의 합은 10.

• 나무의 합 10은 필요한 합 7보다 작다. 절단기의 범위는 14 < x < 19. 나무 합 범위는 1≤ y < 10.

• 범위를 좁히면 중간 값은 16, 나무 합은 5. 나무 합 범위는 5< y < 10 / 절단기 범위는 14< x < 16.

• x에 해당하는 절단기는 15임을 알 수 있고, 절단기 15의 나무 합은 7.

• 이렇게 절단기의 범위를 계속 좁혀나가면서 나무 합을 구하다보면 원하는 나무 합에 도달하게 되고, 그때의 절단기 범위에 속한 숫자가 답이 된다.

[구현 시 주의점]

• 절단기의 중간 값을 찾으면서 범위를 좁히는 건 알겠는데, 절단기의 높이로 나무 합을 구할 때 '전체 나무의 개수가 많아서' 시간이 오래 소요될 수 있다.

아래의 방법으로 시간을 줄일 수 있다.
1. 나무 리스트를 내림차순으로 정렬하고 절단기와 나무 높이의 차(개별 나무 자르는 높이)를 구하고 그 차의 누적합을 만들어갈 때, 중간 과정에서 이미 최종적으로 구하려는 나무 합(이 예시에서는 7)보다 큰 것을 알 수 있으면 그 과정에서 종료할 수 있다.

• 왜냐하면 이미 최종적으로 구하려는 나무 합보다 크기 때문에 절단기 높이는 더 작을 것이고,(절단기 높이가 더 작을 수록 나무 합이 커진다.) 절단기 높이를 줄여나갈 수 있는 요지를 충족하기 때문이다.

2.'절단기가 자를 수 있는 나무 높이의 합'과 (절단기 * 그 나무들의 개수)의 차를 구한다 = 최종적으로 구하려는 합

테스트 케이스

2 11
10 10
정답 : 4

===

3 1
1 2 2
정답 : 1

===

1 1
1000000000

정답: 999999999

코드(4936ms)

import sys
op_lst = list(map(int, sys.stdin.readline().split()))
tree_lst = sorted(list(map(int, sys.stdin.readline().split()))) 
# 주어진 나무들의 높이 리스트

tree_cnt,target_tree_h = op_lst[0],op_lst[1] 
# 나무의 수 / # 집에 가져가려고 하는 나무 길이
tree_max = max(tree_lst) # 나무 중 가장 큰 나무 높이

# 잘라진 나무의 합과 목표 합을 비교
def get_tree_sum(cutter_h):
    tree_sum = 0
    for i in range(tree_cnt-1,-1,-1):
        tree_sub = tree_lst[i]- cutter_h
        if tree_sub <= 0 :
            tree_sub = 0
        tree_sum += tree_sub

        if tree_sum > target_tree_h:
            break
    return tree_sum

cutter_start = 0
cutter_end = tree_max -1

while True:
    cutter_median = (cutter_start+cutter_end)//2
    sum_by_cutter = get_tree_sum(cutter_median)
    
    if sum_by_cutter == target_tree_h:
        print(cutter_median)
        break
    elif sum_by_cutter > target_tree_h:  # 시작 범위 ~ val로 범위를 좁힌다.
        cutter_start = cutter_median -1

    elif sum_by_cutter < target_tree_h: # val ~ 끝 범위로 범위를 좁힌다.
        cutter_end = cutter_median -1
    
    if cutter_start > cutter_end: # 이 코드에서는 start와 end가 교차하는 일이 없어야 하기 때문에 꼭 필요한 코드는 아님.
        print(cutter_median)
        break