[Baekjoon] 2805번 : 나무 자르기 (Python, 이분 탐색)

[Baekjoon] 2805번 : 나무 자르기 (Python, 이분 탐색)

 

목차

 

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

2805번: 나무 자르기

Python

 

방법 1 - 메모리 148396KB / 시간 4796ms / 코드 길이 330B

 

1654번 문제와 동일하다.

https://aigong.tistory.com/397

[Baekjoon] 1654번 : 랜선 자르기 (Python, 이분 탐색)

 

다만 어이없는 것은 동일한 문제인데 시간 초과가 난다는 것이다.

 

import sys
input = sys.stdin.readline

위 코드를 추가함으로써 간신히 코드 통과

희한하다. 

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
l = sorted(list(map(int, input().split())))
start, end = 1, l[-1]

while start <= end:
    mid = (start+end)//2
    cl = 0
    for i in l:
        if i > mid:
            cl += i-mid

    if cl >= m:
        start = mid + 1
    else:
        end = mid - 1
print(end)

 

방법 2 - 메모리 148412KB / 시간 2948ms / 코드 길이 271B

 

sys 없이 sumation을 다른 방식으로 진행했더니 더 빨라진 후 통과하였다.

희한.

 

n, m = map(int, input().split())
l = list(map(int, input().split()))
start, end = 1, max(l)

while start <= end:
    mid = (start+end)//2    
    cl = sum(i-mid if i>mid else 0 for i in l)
    if cl >= m:
        start = mid + 1
    else:
        end = mid - 1
print(end)