[백준 2805번] 나무 자르기 - 이분탐색 예제

 

# 오늘은 오후 약속이 있어 한문제만 딱 풀고 나가려했는데.. 처음 짠 코드는 항상 정답이 아니다..

 

-- 처음 짠 코드

# 필요한 나무 m미터
# 절단기에 지정할 높이 H 의 최댓값을 구하기

N, M = map(int, input().split())
tree = list(map(int, input().split()))

height = 0 # 절단기에 설정할 높이


while True:
    tree_check = 0 # 반복때마다 가져갈 수 있는 나무의 양 체크
    for i in range(N):
        if tree[i]-height>0:
            tree_check += (tree[i]-height)
        else:
            continue # 설정한 높이보다 주어진 나무가 낮다면 0
    if tree_check < M:
        break
    else:
        height += 1

print(height-1) # 높이가 안될때를 마지막으로 체크했기 때문에 -1

처음 마음이 가는대로 코드를 짜봤지만 제출 결과는 시간 초과였다. 아무래도 나무의 수와 길이가 각각 100만, 20억 단위라서 while을 통해 하나씩 비교하는데 너무 오랜시간이 걸리는 것같다. ( 그럼 높은 경우의 예시랑 답도 주면 참 오류 파악이 쉬울텐데 말이지 ) 

 

10억 밀리미터도 아니고 저렇게 높은 나무가 어딨을까

 

뭐 암튼 하나씩 반복을 하지 않고 어떤식으로 풀 수 있을지를 고민해보았다.

 

시작 heigth를 주어진 값의 min부터 시작할 경우 -> 소수의 길이 짧은 나무가 주어질 경우 무용지물

등등을 생각하다가

 

주어진 tree 리스트에서 max의 값부터 하나씩 내려가며 그 때 얻어갈 수 있는 tree_check를 하고 만약 tree_check가 주어진 M보다 클 경우 그때의 height값에서부터 다시 하나씩 증가시켜가면며 tree_check를 하면 조금더 빨리 계산할 수 있겠다!!

 

-- 해서 다시 짠 코드

 

N, M = map(int, input().split())
tree = list(map(int, input().split()))
tree = sorted(tree, reverse = True) # max값부터 확인하기 위해 역정렬

height_index = 0 # height를 위의 값부터 판단할 index

while True:
    height = tree[height_index]
    tree_check = 0  # 반복때마다 가져갈 수 있는 나무의 양 체크
    for i in range(N):
        if tree[i] - height > 0:
            tree_check += (tree[i] - height)
        else:
            continue

    if tree_check >= M:
        break
    else:
        height_index += 1

height = tree[height_index]

while True:
    tree_check = 0 # 반복때마다 가져갈 수 있는 나무의 양 체크
    for i in range(N):
        if tree[i]-height>0:
            tree_check += (tree[i]-height)
        else:
            continue # 설정한 높이보다 주어진 나무가 낮다면 0
    if tree_check < M:
        break
    else:
        height += 1

print(height-1)

하지만 다시 시간 초과에 걸려버리고..

이번에 든 생각은 중간에 있는 for문이 N이 커질경우 그 경우의 수가 너무 많아지나??라는 생각이었다. 따라서 이를 수정해보았다.

 

N, M = map(int, input().split())
tree = list(map(int, input().split()))
tree = sorted(tree, reverse=True)  # max값부터 확인하기 위해 역정렬

height_index = 0  # height를 위의 값부터 판단할 index


def minus_tree(n):
    if n - height > 0:
        return n - height
    else:
        return 0


while True:
    height = tree[height_index]
    tree_check = 0  # 반복때마다 가져갈 수 있는 나무의 양 체크

    tree_check = sum(list(map(minus_tree, tree)))  # tree리스트에 해당 값을 뺀 결과를 기록하고 sum

    if tree_check >= M:
        break
    else:
        height_index += 1


height = tree[height_index]

while True:
    tree_check = 0 # 반복때마다 가져갈 수 있는 나무의 양 체크

    tree_check = sum(list(map(minus_tree, tree)))


    if tree_check < M:
        break
    else:
        height += 1

print(height-1)

하지만 아직도 5%에서 시간 초과가 걸린다.. 마지막 남은 방법은 이분탐색 알고리즘 인것 같다. 첫날 백준을 풀 때 공부를 했던 이분탐색 알고리즘을 활용해보자.

 

 

-- 완성된 정답코드

import sys

N, M = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))

start = 1
end = max(tree)

while start <= end:
    tree_check = 0 # 가져갈 수 있는 나무의 양
    height = (start + end) // 2 # 중간부터 탐색!!

    for i in tree:
        if i > height:
            tree_check += (i - height)


    if tree_check >= M: # 가져갈 수 있는 나무의 양이 많은 경우 height를 더 높여도 된다
        start = height + 1
    else:
        end = height -1  # 반대의 경우 나무의 양을 늘리기 위해 height를 줄여야 한다

print(end)

이분탐색 알고리즘을 짜고도 계속 시간초과가 나와서 사소한 것들을 다 바꿔주었다.

 

1. else: continue 삭제 -> 실제로 시간에 영향을 주는 지는 모르겠지만 뺐다 -> 추후에 정답코드에 넣어서 돌려봤더니 시간초과

2. for문을 인덱스로 받아주던걸 in으로 값 자체를 받아주도록 변경 -> 제일 마지막에 바꿔준 것으로 영향이 있음!!

3. input() 을 sys.stdin.readline으로 변경 ( 한번만 입력받긴 하지만 조금이라도 더 빨라지게 하기 위해 )

 

def minus_tree(n):
    if n - height > 0:
        return n - height
    else:
        return 0



tree_check = sum(list(map(minus_tree, tree)))

이 코드를 사용해서도 마지막에 다시 한번 제출 해봤는데 정답이 되었다 !! 사용자 지정함수로 만들고 계산하는 것도 시간 절약에 도움이 되는듯하다.

 

 

오늘도 성공적으로 상근이에게 필요한 나무를 잘라주었다.