[백준] 2805 나무 자르기 python파이썬

• 문제링크: https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

• 유형: 이진탐색 (이분탐색)

알고 계시지만 잘 기억 안나는 분들을 위해 이분탐색에 대해 간단히 말하면, 범위에서 중간 값을 해보고, 그에 따라 범위를 수정하고, 이를 반복하는 것이다.

아예 모르시면 검색해보는 것을 추천드립니다...!

 

• 답안

import sys
# input 값 받기
N, M = map(int, sys.stdin.readline().split())
height = list(map(int, sys.stdin.readline().split()))

# 처음 범위 설정
lo, hi = 0, max(height) # max()를 하면, 범위가 더 좁아질 수 있다는 장점이 있지만, 연산을 한번 더 해야하는 것이므로, max대신 1000,000,000을 사용하는 것도 좋다. (나무의 최대 길이)

# 반복
while lo <= hi:
    mid = (lo + hi) // 2 # 중간 값
    logsum = 0 # 해당 중간 값으로 했을 때, 나오는 나무의 양을 담기 위한 변수
    
    for i in height: # 각 나무들 체크 
        if i > mid: # 해당 나무길이 (i)가 자르는 위치보다 커야지만, 나무를 자를 수 있으므로
            logsum += i - mid #자른 나무 길이 더해주기
    
    # 범위 재조절
    if logsum >= M: # 잘린 나무가 많으면 자르는 위치를 더 높여서 덜 잘라도 되니까
        lo = mid+1
    else:
        hi = mid-1
        
print(hi)

 

사실 처음엔 아래처럼 코드를 짰는데, 그러면 if문이 하나 더 들어가서(무한루프) 위에 코드가 훨씬 대중적인 코드인 것 같다. 

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

lo, hi = 0, max(height)

while lo < hi:
    mid = (lo + hi) // 2
    logsum = 0
    
    for i in height:
        if i > mid:
            logsum += i - mid
            
    if logsum >= M:
        if mid==lo:
            break
        lo = mid
    else:
        hi = mid
        
print(lo)