[Python] 백준 2805번 - 나무 자르기

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

2805번: 나무 자르기

 

처음에 while문 하나 for문 하나를 사용해서 O(N^2) 으로 풀었다.

코드 짜면서 뭔가 무조건 시간초과 날 것 같다고 생각했는데 역시나...

 

이분탐색으로 다시 풀었다.

 

그런데 웃긴 점은.. 오늘 백준 자체가 느린 것인지..?

같은 코드로 제출했는데 한 번은 맞고 한 번은 시간초과가 난다.

 

혹시나 내가 틀린 걸까 싶어서 구글링 해보았는데 다른 사람들과 내 코드가 똑같다.

...백준 문제인걸로.

 

 

#이분탐색코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
tree = list(map(int, input().split()))

s, e = 1, max(tree)

while s <= e:
    mid = (s + e) // 2
    lth = 0
    for i in tree:
        if i > mid:
            lth += (i - mid)
    if lth >= m:
        s = mid + 1
    else:
        e = mid - 1

print(e)

 

 

#시간초과코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
tree = list(map(int, input().split()))

ans = max(tree)
lth = 0
while True:
    for i in tree:
        if i > ans:
            lth += i - ans
    if lth == m:
        break
    ans -= 1
    lth = 0

print(ans)