2805

날짜 : 2022. 12. 09

사용 언어 : python

 

문제

 

 

코드

import sys

n, m = map(int, sys.stdin.readline().split())  # 나무의 개수, 나무의 길이
t = list(map(int, sys.stdin.readline().split()))  # 각 나무의 길이
start = 0
end = max(t)
while start <= end:
    mid = (start + end) // 2  # 자를 높이
    total = 0  # 잘랐을 때의 길이
    for i in range(n):
        if (t[i] - mid) > 0:  
            total += t[i] - mid
    #print(mid, total)
    if total == m:
        print(mid)
        exit()
    if total > m: start = mid + 1  # 자른 길이가 원하는 길이보다 큰 경우
    else: end = mid - 1  # 원하는 길이보다 짧은 경우
print(end)

 

 

풀이

- 자를 높이를 기준으로 for문을 돌린다.

- 자른 길이의 총합이 원하는 길이보다 큰 경우, 높이를 늘림으로써 길이를 줄인다.(start = mid + 1)

- 이 과정을 binary search 를 통해 시간복잡도를 최소화하고, 아웃풋을 출력한다.

 

 

알게된 점

- 일반 linear 한 for문의 시간복잡도(while문 내부 for문) : O(n)

- binary search의 시간복잡도 : O(logn)

=> 이 문제에서의 최종 시간복잡도 : O(nlogn)

 

 

참고 사이트

-