[BaekJoon] 2805 나무자르기

[출처 : https://www.acmicpc.net/problem/2805]

 

 

n, m = map(int,input().split())

treeHeight = list(map(int, input().split()))

# 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
treeHeight.sort()
resultList=list()

def binarySearch(data, m2):
    low = 1
    # m은 1<= m <= 2,000,000,000
    high = data[len(data)-1]
    # n도 1이상이기에 입력된 데이터중 가장 큰값의 경우 그 값보다 1 더 작은값부터 그 밑의 값까지 탐색하면 되므로 가장 큰값을 끝값으로 지정해주면 된다.
    result = 0

    while low <= high:      
        mid = (low + high) // 2
        # 여기서의 mid 값이 절단기에 설정할 높이 H
        totalM = 0
        for tree in data:
            if tree > mid:
                totalM += (tree - mid)
            # tree길이가 mid 보다 클때만 빼주도록 조건문 설정 => totalM에 음수값을 더하지 않도록

        if totalM >= m2:
            # mid(H) 값을 높여서 탐색해야함
            if result < mid :
                result = mid
            low = mid + 1
        else:
            high = mid - 1
    return result

#print(max(resultList))
#이렇게 max () 를 사용했을때 콜스택 초과가 나는 경우가 있을 수도 있음 따라서 값을 계속 변경해줄것.
# mix 나 max의 인자에 제한이 없는것 같지만 실제 인자가 무수히 많아지게 된다면 콜스택 초과 에러가 발생할 수 있다.

print(binarySearch(treeHeight, m))

 

문제풀이

 

1. 초기 입력 처리 => treeHeight에 나무 길이 저장

2. 이진탐색 메서드 구현 => 나무의 길이는 최소 1이기 때문에 1 ~ 최대값까지 탐색

3.  나무가 mid 보다 클때 나무의 길이에서 mid를 빼준값을 tatalM에 저장하고 totalM이 기준값 m2 보다 클때 result와 mid 값을 비교 => 여기서 result의 최소값을 찾아야하기에 result에 mid 값을 저장

4. 이후 결과를 출력

 

+) 초기 결과 출력에 있어서 모든 가능한 mid 값의 결과를 resultList에 저장하고 max 혹은 min을 이용해 출력해주면 간혹 runtime error 가 발생할 수 있다. 이는 콜스택 초과 오류가 발생한 경우이기 때문에 가능한 사용을 자제하는 것이 좋다..(그래도 사용할 수 있으면 해야겠지만)