[백준] 2805 파이썬(python) : 나무 자르기 - (★)

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

2805번: 나무 자르기

 

 

pypy3로 제출해야 정답판정을 받을 수 있습니다.

 

import sys
n, m = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))
res = 0
start, end = 1, max(tree)
while start <= end:
    mid = (start+end)//2
    tmp = 0
    for i in tree:
        if i > mid: #1
            tmp += (i - mid) #2
    if tmp >= m:
        res = mid #3
        start = mid + 1
    else:
        end = mid - 1
print(res)

 

#1 : 절단기로 자르고 남은 부분을 가져가는 것이기에 나무인 i가 절단기 mid보다는 커야한다.

#2 : 자른 부분 모두 더하기

#3 : 적어도 m만큼은 길이를 얻어야 하기 떄문에 tmp >= m일때가 당장의 최적 반복할 수록 점점 갱신된다.

 

1654번 랜선 자르기(https://hgk5722.tistory.com/138)

랜선 자르기와 비슷한 문제였다. 차이가 있다면 랜선은 자르고 개수를 세어주는것이고 이 문제는 자르고 남은 길이를 가져가는것의 차이가 있다.