백준 2805번(나무 자르기) 파이썬

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

2805번: 나무 자르기

이 문제는 이분탐색의 "응용" 문제이다.

저번에 풀었던 [수 찾기] 문제 보단 어려웠지만 다 풀고나니 할만 했던거 같다.

이 문제는 가장 긴나무를 end로 하고 그 중간값을 mid로 하여 각각의 나무의  mid부터 end까지의 길이의 합을 더하여 m보다 크거나 같을 경우 mid는 조건에 부합하는 절단선의 높이이기 때문에 answer 리스트에 넣어준다 그 다음 아래 코드를 따라가 조건에 맞게 재귀를 돌리다 보면 answer에서 가장 큰 값이 절단선의 최댓값이 되어 정답을 도출 할 수 있다.

 

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
array = list(map(int,input().split()))
array.sort() # 이분탐색은 정렬이 기본이다.
answer = [] # 적어도 m미터를 절단할수 있는 절단기의 높이들을 담을 리스트

def bst(array,m,start,end):
    total = 0
    if start>end:
        return None
    mid = (start+end)//2
    for i in range(len(array)): # 각각의 나무들에 대해 비교를 해줘야한다
        tmp=array[i]-mid #나무의 높이에 절단기의 높이를 뺀다
        if tmp>=0: # 잘랐을때의 나무의 길이가 0보다 크거나 같으면
            total+=tmp # total에 더해준다
    if total >= m: # total이 m보다 크거나 같을경우 조건에 부합하기 때문에
        answer.append(mid) # answer 리스트에 넣어준다
        return bst(array,m,mid+1,end) # 그리고 조건에 부합했던 절단기의 높이를 start로 삼아 재귀를 돌려 또 이분탐색을 해준다
    else:
        return bst(array,m,start,mid-1)

bst(array,m,0,array[-1])
print(max(answer)) # 조건에 부합하는 요소들중에 최댓값을 출력한다.

문제에 있는 예제들은 다 정답이 나오는데 이상하게 39%에서 "메모리초과" 가 나왔다.

그 이유를 찾다가 처음에  for문 안에있는 total을 구하는 과정을 리스트로 만들어 구했었다.

이 부분에서 쓸데없이 리스트로 메모리를 잡아먹기 때문에 메모리 초과가 나는것을 알았다.

위의 코드와 같이 고치니까 바로 정답이 떠서 다행이었다.

하지만 이런 기초적인거도 실수하는 내가 아직은 아쉽다.

이러한 실수들을 줄여가는게 앞으로의 숙제인거 같다.