[BOJ / 백준] 2805번 나무 자르기 python / 파이썬 이진탐색

 

---

세상에서 가장 킹받는 단어, 그건 바로 시간 초과

 

우선 입력을 그냥 input으로 받아주면 시간 초과 나는 듯하다... 

시간 초과로 안풀렸던 문제들 input 받는 방법만 바꿔줬더니 두 문제나 풀렸다.. 하핳..;;;

 

이 문제도 import sys 해주고, stdin.readline으로 해보세요~

 

1. 문제 읽기

적어도 M미터를 가져가는 높이 H의 최댓값 찾기

 

2. 설계

H만큼 잘랐을 때 되냐 안되냐를 찾는건데, 이 H 중에 최댓값을 찾는거니까 이진 탐색으로 풀어준다.  

 

 

import sys

def check(x): # M보다 크거나 같은지 확인하는 부울형 함수
    ans = 0
    for i in trees:
        if i > x: # H보다 작은 경우는 음수 나오니까 제외
            ans += i-x
    return ans >= M # True/False 반환


N, M = map(int, input().split())
trees = list(map(int,sys.stdin.readline().split()))

s = 0
e = 1000000000 # 문제에서 가장 큰 수 주어짐
ans = 0
while s <= e:
    mid = (s+e)//2
    if check(mid): # True일 때
        ans = mid
        s = mid + 1
    else: # False 일 때
        e = mid - 1
print(ans)

 

실버 3이 된 나, 제법 멋져요^^...

 

현실은...

교수님 : 옥상 아니 광장으로 따라와

네...ㅜ ㅜ