[Python]백준 BaekJoon.AC 2805 : 나무 자르기(python3으로)

 

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

2805번: 나무 자르기

 

 

 

정답률이 무척 낮은 문제였는데, python3 정답률은 평균보다도 낮았고, 내가 그 정답률을 더 낮추는데에 기여했다!...

 

 

pypy3로 풀란 말이 있었지만 python3로 풀고 싶었다..

 

 

 

 

이진탐색 알고리즘으로 간단히 구현했지만 시간초과로 빠르게 광탈했고,

여러 코드를 참고해봤지만 도통 시간초과는 풀리지 않았다.

 

 

sort도 없앴고, min과 max도 없앴고. list comprehension 빼고 다 해봤는데도 안됐다.

 list comprehension이 뭔가 싶어 찾아봤더니, 이미 아는 내용인데 용어 이름을 모르고 있었다. 내겐 흔한 일이다ㅎ..

 

 

 

 

결국 함수를 이용해 풀어줬다.

함수를 이용하면 시간이 더 증가할 줄 알았는데, 간단한 함수 구현은 오히려 시간을 단축시켜주는 것 같다.

 

 

↓ 파이썬에서 함수가 더 효율적일 수 있는 이유 ↓

https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function

 

 

 

 

요약하자면, 파이썬은 function을 바이트코드로 컴파일 하기 때문이라고...

전역변수로 계산해주는것보다, 함수를 만들어 지역변수로 처리해주는게 시간이 덜 소요된다고 한다.

 

 

 

그리고 함수로 처리해주니 거짓말처럼 통과가 됐다.

 

코드도 더 길어지고 함수 처리를 해주기까지 해야 하는데도 시간이 줄어들다니.

미세한 차이가 다른 결과를 가져왔다. 염두해둬야겠다...

 

 

 

 

그리고 처음엔 min(중간값)과 sta(최솟값)를 출력해줬는데, 자꾸 틀렸다고 뜨길래 fin으로 바꿔줬다.

특정 문제에서 답이 1씩 더 증가돼 나오는 걸로 짐작했을 때,

while 내 if문을 지나면서 마지막 불필요한 순간까지 계산을 해줘서 그렇지 않나 생각하고 있다.

 

 

 

 

import sys

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

sta = 0
fin = sys.maxsize

def checksum(mid):
    sum = 0
    for t in tree:
        if t > mid:
            sum = sum + t-mid
    return sum

while sta <= fin:
    mid = (sta+fin) // 2

    sum = checksum(mid)

    if sum>=M: #너무 많이 잘랐다, 자르는 높이 높혀야 함, sta(나무 길이의 최솟값) 늘려야 함
        sta = mid + 1
    elif sum<M: #너무 조금 잘랐다, 자르는 높이 낮춰야 함, fin(나무 길이의 최댓값) 줄여야 함
        fin = mid - 1

print(fin)