[BOJ] 백준 2805 나무 자르기 / 이분탐색

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

 

자를 수 있는 최소 높이인 1 부터 max(나무의 높이 배열) 사이에서 최소 m미터 길이의 나무를 가져가기 위해

이분탐색을 진행하며 m을 찾아나가는 문제이다.

 

자른 나무 길이의 합을 구하기 위해 최악의 경우 100만 번의 sum 연산이 log(10⁹) 만큼 반복된다.

이 풀이도 시간 초과가 발생하지는 않지만

Counter를 사용해서 100만 번의 연산을 감소시켜 시간을 줄이는 풀이를 찾게 되었다.

 

 

 

구현 언어: Python

 

 

1. 내 풀이

import sys

r = sys.stdin.readline


def binary_search(m, trees):
    answer = 0
    left = 1
    right = max(trees)

    while left <= right:
        mid = (left + right) // 2
        total_cut = sum(map(lambda x: x - mid if x >= mid else 0, trees))
        if total_cut >= m:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    return answer


n, m = map(int, r().split())
trees = list(map(int, r().split()))
print(binary_search(m, trees))

 

2. Counter를 활용

from collections import Counter
import sys

r = sys.stdin.readline


def binary_search(m, trees):
    answer = 0
    left = 1
    right = max(trees)

    while left <= right:
        mid = (left + right) // 2
        total_cut = sum((tree - mid)*cnt for tree, cnt in trees.items() if tree > mid)

        if total_cut >= m:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    return answer


n, m = map(int, r().split())
trees = Counter(map(int, r().split()))
print(binary_search(m, trees))

 

이 결과 약 7배정도 속도가 빨라진 것을 확인할 수 있었다.