[Baekjoon Online Judge] 백준 2805번 나무 자르기(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2805번 나무 자르기

(Python)

(글쓴날 : 2020.04.04)

 

---

* Baekjoon Online Judge, 백준 2805번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2805번 나무 자르기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

---

2) 풀이 과정

나무들의 높이가 주어지고, 각 나무들을 절단기를 통해 같은 높이로 자를 때 원하는 나무의 길이를 만족하는 절단기 높이의 최댓값을 출력하는 문제입니다.

 

저의 경우, 이분 탐색 알고리즘인 파라메트릭 서치를 적용하여 문제를 해결했습니다.

먼저, 나무의 최저 높이와 최고 높이를 구해, 최저 높이가 최고 높이 보다 작거나 같을 때까지 반복문을 돌리고 해당 값들의 중간 값을 절단기의 높이로 지정합니다.

만약, 절단한 나무길이의 합이 원하는 길이 보다 작다면 최고 높이를 중간값 - 1로 지정해 다시 반복하고, 크다면 가장 큰 중간값을 갱신해 저장한 뒤 최저 높이를 중간값 + 1로 지정하여 반복합니다.

그렇게 계속 반복하다가 만약 원하는 나무길이와 딱 떨어진다면 해당 중간값이 절단기에 설정할 수 있는 최댓값이므로 출력 후 바로 종료하고, 그렇지 않고 반복문을 빠져나왔다면 저장되어 있는 가장 큰 중간값이 절단기에 설정할 수 있는 최댓값이 됩니다.

 

제 방식은 Python 3로 제출 시 시간 초과가 발생하며, PyPy3로 제출 시 정답으로 인정됩니다.

요새 들어, PS 언어를 Python에서 C++로 갈아타야 하나 고민이 됩니다...

---

3) 코드

 

* Python 코드(PyPy3)

import sys
input = sys.stdin.readline
 
N, M = map(int, input().split())
trees = list(map(int, input().split()))
left = 0
right = max(trees)
maxCut = 0
 
while left <= right:
    getTree = 0
    mid = (left + right) // 2
 
    for tree in trees:
        if tree - mid < 0:
            continue
        getTree += tree - mid
 
    if getTree == M:
        print(mid)
        sys.exit()
    elif getTree < M:
        right = mid - 1
    else:
        if maxCut < mid:
            maxCut = mid
        left = mid + 1
        
print(maxCut)

---