[Search] 2805번 - 나무 자르기 (23일차)

#코드 실행 시간 단축을 위한 sys 모듈 import
import sys
input = sys.stdin.readline
#나무의 개수와 필요한 나무의 길이를 입력
n,m = map(int, input().split())
#각 나무의 길이를 입력받아 리스트로 저장
tree = list(map(int, input().split()))
#나무 리스트 끝에 0을 추가(가장 작은 나무~0까지의 높이를 다루기 위함)
tree.append(0)
#나무 리스트를 내림차순으로 정렬
tree.sort(reverse=True)

#필요한 나무의 길이를 얻기 위해 나무를 자르는 높이를 찾는 함수
def find():
    #해당 높이로 나무를 잘랐을 때 얻을 수 있는 나무의 길이를 저장하는 변수
    cnt = 0
    #나무를 자르는 높이를 저장하는 변수(시작점인 가장 높은 나무의 높이로 저장)
    cut = tree[0]
    #각 나무의 순서에 대해
    for i in range(n):
        #해당 순서의 나무의 높이와 다음 순서 나무의 높이의 차이만큼 반복
        for j in range(tree[i]-tree[i+1]):
            #나무를 자르는 높이를 1씩 줄여가며 (20->19->18....)
            cut -= 1
            #얻을 수 있는 나무의 길이를 업데이트
            #i번째 나무 ~ i+1번째 나무 사이에서는 자르는 나무의 높이가 1 내려갈 때마다
            #얻을 수 있는 나무의 길이가 i만큼 증가한다
            cnt = cnt + (i+1)
            #만약 얻을 수 있는 나무의 길이가 필요한 길이와 같거나 더 커졌을 때
            if(cnt >= m):
                #해당 높이를 출력한다
                print(cut)
                #함수 종료
                return
#함수 실행
find()

#인사이트
#이분 탐색으로 풀이 시 0~가장 높은 나무의 높이 각각에 얻을 수 있는 나무의 길이를 저장한 뒤
#이분 탐색으로 필요한 나무의 길이와 같은 값을 찾거나 탐색 종료 지점에서 start와 end 중
#더 큰 값을 반환하는 식으로 구현하나 그 비효율성이 지나치게 크다(메모리도 잡아먹는다)
#따라서 순차 탐색으로 전환해 시간 효율성과 메모리 효율성을 확보했다