[Solved] BOJ: 2805 | 나무 자르기

문제

여러 높이의 나무들이 주어지고
같은 높이로 이 나무들을 잘라서 최소 M미터 이상의 나무를 확보하고자 한다.

입력과 출력

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

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

---

문제 해결 요약

적절한 절단 높이를 탐색하면서 최소 M미터 이상의 나무를 확보해야한다.
시간 복잡도를 줄이기 위해 이진탐색을 이용해야한다.

코드 설명

import 및 입력받기

-

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
trees = list(map(int, input().split()))

• 나무 개수 n, 최소한 가져가야하는 나무 길이 m
• n개의 나무들을 리스트로 받아낸다

이진 탐색 구현

m을 넘길 수 있는 최대한의 height를 구하기 위해 이진탐색을 구현한다.

-

end = max(trees)
start = 0

while end >= start:
    height = (start + end) // 2
    tmp = 0
    for tree in trees:
        if tree >= height:
            tmp += (tree - height)
    if tmp >= m:
        start = height + 1
    else:
        end = height - 1

print(end)

• end값을 trees의 최대값으로, start값을 0으로 초기화
• end와 start가 서로 수렴할 때까지 while문을 돌면서
• height는 start와 end의 중간값으로 지정
• trees리스트에 존재하는 tree에 대하여
• tree의 길이가 height보다 크거나 같다면 (그냥 크거나로 해도될거같다)
• tmp에 tree - height 값을 더해준다
• 만약 tmp가 목표로 하는 나무 길이인 m 보다 크거나 같다면
• height의 값을 더 높게 설정해볼 수 있을거 같다.
• 따라서 start의 값을 height + 1로 갱신해준다.
• 반대로 tmp가 목표하는 나무 길이인 m 보다 작다면
• height의 값을 더 낮게 설정해야 최소한의 목표하는 나무 길이를 획득할 수 있다.
• 따라서 end의 값을 height - 1로 갱신해준다.

---

전체 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
trees = list(map(int, input().split()))

end = max(trees)
start = 0

while end >= start:
    height = (start + end) // 2
    tmp = 0
    for tree in trees:
        if tree >= height:
            tmp += (tree - height)
    if tmp >= m:
        start = height + 1
    else:
        end = height - 1

print(end)

+ 시간 초과 났던 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
trees = list(map(int, input().split()))

height = max(trees)
tmp = 0
while m > tmp:
    tmp = 0
    for tree in trees:
        if tree > height:
            tmp += (tree - height)
    if tmp >= m:
        break
    height -= 1

print(height)