[백준 2805번] 나무 자르기

2020. 7. 22. 13:05Algorithm/practice

https://www.acmicpc.net/problem/2805

 

2805번: 나무 자르기

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

www.acmicpc.net


문제 접근 및 해결 방법

구해야 하는 값을 알고 있다. 이는 구해야 하는 값에 근접하기 위해 유추하는 과정이 필요하다. 이에 따라 이분 탐색을 이용하여 문제를 풀어보았다.

Python 시간초과! pypy3로 바꿔 제출했더니 통과되었다. Python 으로 풀 수 있는 방법은 없을까?..


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
n, length = map(int, sys.stdin.readline().strip().split())
trees = list(map(int, sys.stdin.readline().strip().split()))
answer = 0
# left 는 자를 수 있는 최소 높이
# right 는 자를 수 있는 최대 높이
left, right = 0, max(trees)
while left <= right:
    total = 0
    mid = (left + right) // 2
    for tree in trees:
        # 나무가 mid 값보다 클 때 자른다
        total += tree - mid if mid < tree else 0
    # 자른 총 나무길이가 가져가야할 나무길이보다 적을 때
    # 잘라서 나오는 총 나무길이를 늘려주기 위해 자르는 나무 길이를 줄여야 한다
    # right 를 mid - 1로 줄인다.
    if total < length:
        right = mid - 1
        continue
    # 목표는 주어진 나무길이를 구할 수 있는 '제일 긴' 나무길이를 구해야한다.
    # 이에 따라 answer 가 mid 보다 작으면 answer 에 mid 값을 할당한다.
    answer = mid if answer < mid else answer
    # 자른 총 나무길이가 가져가야할 나무길이보다 많기 때문에
    # 잘라서 나오는 총 나무길이를 줄여주기 위해 자르는 나무 길이를 늘려야 한다.
    # left 를 mid + 1로 증가시킨다.
    left = mid + 1
print(answer)

 

'Algorithm > practice' 카테고리의 다른 글

[백준 9935번] 문자열폭발  (0) 2021.07.05
[백준 11005번] 진법변환2  (0) 2020.07.10
[백준 1181번] 단어정렬  (0) 2020.07.09
[백준 2446번] 별찍기-2446  (0) 2020.07.08
[백준 2523번] 별찍기-13  (0) 2020.07.08