[테스트케이스 모음] 백준 2805번 : 나무자르기 python, 파이썬

1. 문제

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

2805번: 나무 자르기

 

 

 

2. 풀이

binary search

 

 

 

3. 구현

import sys
#sys.stdin = open('input.txt')

n,m =map(int,sys.stdin.readline().split())
lis = list(map(int, sys.stdin.readline().split()))

le=1
ri=max(lis)

while le<=ri:
    mid = (le+ri)//2
    total= [tree-mid if tree>mid else 0 for tree in lis]
    # print(total)
    total_val = sum(total)
    # for tree in lis:
    #     if tree>mid:
    #         total+=(tree-mid)
    if total_val>=m:
        le=mid+1
    else:
        ri=mid-1

print(ri)

 

 

4. 테스트케이스 백준 모음

@paa0609 님

2 11
10 10

정답 : 4

3 1
1 2 2

정답 : 1

 

@wjsqjawns님

4 10
1 4 5 7

정답:
2

5 2000000000
900000000 900000000 900000000 900000000 900000000

 

정답: 500000000

 

1 1000000000
1000000000

답: 0

 

1 1
1000000000

답: 999999999

 

 

--- 추가한 테스트케이스---

6 12
19 9 18 20 17 8

답: 15

 

5 14
4 22 10 16 36

답: 22