2805 나무 자르기

💡문제 분석 요약

• 나무개수, 원하는 나무 길이, 각 나무들의 길이가 주어졌을 때 바닥에서부터 몇m가 되는 지점을 베어야 나무의 윗부분들을 잘라내어서 정확히 내가 원하는 나무의 길이만큼 베어갈 수 있는지를 구해야한다.
• 중요한 것은 절단기가 아래서부터 시작한다는 것이다. 즉, 맨 아래를 자르는 것이 가장 많은 나무를 가져가는 경우이다.

💡알고리즘 설계

• 나무가 아닌 절단기를 대상으로 이분탐색을 진행한다.

💡코드

처음에 틀린 풀이이다. (아래 설명)

n, m = map(int, input().split())
tree = sorted(list(map(int, input().split())))

# 절단기의 높이를 이분탐색으로 찾기
# 절단기 높이는 짧을수록 나무를 더 많이 자르는 것임. (중요)

def checkSum(mid): # 절단기 높이가 mid일 때 나무 자르면 내가 몇m의 나무를 가져가는지 체크하는 함수
    sum = 0
    for i in range(n-1, 0, -1):
        if tree[i]-mid < 0:
            return sum
        sum += (tree[i]-mid)
    return sum


def binarySearch(n, m):
    left = tree[0]
    right = tree[-1]

    while left <= right:
        mid = (left + right) // 2

        if checkSum(mid) == m:
            return mid

        # mid로 잘랐을 때 나무 합이 m보다 크면 나무 합이 m보다 크다면 더 적게 잘라야함
        if checkSum(mid) > m:
            left = mid + 1
        # mid로 잘랐는데 나무가 부족하면 더 잘라야하니까 right를 내려서 더 잘라야함
        elif checkSum(m) < m:
            right = mid - 1


print(binarySearch(n, m))

💡시간복잡도

• 이분탐색이므로 O(log N)

💡 틀린 이유

• 일단 절단기를 대상으로 이분탐색을 진행하는데, left를 tree의 첫번째로 하는 게 문제였다. 왜냐면 그럼 절단기의 최소가 제일 작은 나무고, 최대가 제일 큰 나무인데 만약에 모든 나무가 다 필요한 경우에는 못하게 되는 것이다. 0부터 시작했어야 가장 밑동을 자르는 경우를 생각할 수 있다.

💡 틀린 부분 수정 or 다른 풀이

• left를 0로 수정하였다.
• 나무에 대한 이분탐색이 아니므로 사실 나무들을 정렬할 필요도 없다.

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

# 나무들 자체에 대해서 높이를 구하는 게 아니고 절단기의 높이를 구하는 거라서 이분탐색을 쓰더라도 정렬을 여기서 할 필요는 없음.
trees = list(map(int, input().split()))

# 절단기의 높이를 이분탐색으로 찾기
# 절단기 높이는 짧을수록 나무를 더 많이 자르는 것임. (중요)

left = 0 # 나무 높이 최소가 0이라서 0으로 설정
right = trees[-1]

while left <= right:
    mid = (left + right) // 2
    sum = 0

    # 각 반복마다 mid값(절단기 높이)을 설정하고, 해당 절단기로 나무들 잘라봄. 잘린 나무들 합이 sum
    for tree in trees:
        if tree-mid > 0:
            sum += (tree - mid)

    # mid로 잘랐을 때 나무 합이 m보다 크면 나무 합이 m보다 크다면 더 적게 잘라야함
    if sum >= m: # 절단기의 "최대높이"를 알아야하므로 sum이 m과 같은 시점이 되어도(탈출조건), 더 진행해서 절단기 높이를 최대한 높여야함!!! (중요)
        left = mid + 1 # 절단기 높이를 더 올림 (더 적은 나무를 자르게 됨)

    # mid로 잘랐는데 나무가 부족하면 더 잘라야하니까 right를 내려서 더 잘라야함
    else:
        right = mid - 1 # 절단기 높이를 더 내림 (더 많은 나무를 자르게 됨)

# right를 출력하는 이유는 left가 right보다 커지는 시점에서 right는 가장 마지막으로 가능한 높이를 의미하기 때문임
print(right)

💡 느낀점 or 기억할정보

• 숫자가 너무 크다면 이분탐색을 의심해볼 것 !!
• 문제의 조건을 읽고 for문의 시작조건을 0으로 할지, 1로 할지 이것을 판단하는 게 매우 매우 중요하다 !!