나무 자르기

문제분석

기본에서 조금 응용된 이분탐색 문제다. 이분탐색을 구현하는 것이 어려웠다기 보단, 길이가 긴 입력에 대해서 시간복잡도를 줄이는 것이 굉장히 힘들었다.

• 먼저 절단기에 설정할 수 있는 최대값은 항상 0과 가장 높은 나무의 높이 사이에 위치함으로, 이분탐색의 왼쪽끝을 0, 오른쪽 끝을 가장 높은 나무의 높이로 설정해 주었다.
• 이 문제에서의 기준은 집에 가져갈 수 있는 나무의 길이이다. 따라서, 절단기 설정값에 따른 가져갈 수 있는 나무의 길이를 구하는 함수를 추가로 만들어 주었다.[TREE]
• 집에 가져갈 수 있는 나무의 길이가 M보다 크다면 l을 mid+1로 업데이트해 다시 탐색을 진행하고, 작다면 r을 mid-1로 업데이트해 탐색을 진행한다.
• 만약 M과 정확히 일치하면, 탐색을 멈추고 while문을 탈출한다.

아래의 코드를 만들기 전에 pypy3로만 통과가 되어 python3로 시간초과가 발생하지 않고 통과할 수 있는 방법이 없을까 하면서 다른 분들의 블로그를 검색해 봤다. 이 과정에서 코드에 함수 사용 유무에 따라서 코드 실행 시간에 영향을 미친다는 것을 확인했는데, 밑에서 더 자세히 설명해 보겠다.

CODE - 최종

import sys
read=sys.stdin.readline
n,tree=map(int,read().split())
num=list(map(int,read().split()))

#이분 탐색의 양끝 r,l
#절단기에 설정할 수 있는 최대값은 항상 0과 가장 높은 나무의 높이 사이에 존재한다.
r,l=max(num),0

#절단기 값에 따른, 가져갈 수 있는 나무의 길이 합을 구하는 함수
def TREE(x):
    sum_tree=0
    for i in num:
        if i>x: sum_tree+=(i-x)
    return sum_tree

while l<=r:
    mid=(l+r)//2
    sum_tree=TREE(mid)
    if sum_tree>tree:
        l=mid+1
        answer=mid
    elif sum_tree==tree:
        answer=mid
        break
    else:
        r=mid-1

print(answer)

pjok1122님의 블로그를 참고하면서 이상한 점을 한가지 발견했다.

이 분의 블로그를 읽고, 내 코드와 변수명 그리고 함수 사용 유무를 제외하고는 다른점이 보이지 않았다. 이 코드를 python3로 제출했을 때, 시간초과가 발생 안하셨나?! 싶어서 복붙해서 다시 제출해 보았다. 그런데 이 코드는 시간초과가 발생하지 않고 통과가 되었다.

혼란스러워져, 내 코드와 다른부분이 없는지 계속 확인해 보았는데 찾을 수 없었다.(함수 사용 여부 제외) 혹시나 싶어서 절단기 설정값에 따른 가져갈 수 있는 나무의 길이를 구하는 부분을 함수로 작성해서 제출해 보았다.(이 코드가 위의 코드입니다.) 그랬더니 시간초과가 발생하지 않고 잘 통과되는 것을 확인할 수 있었다!!

굉장히 당황스러운 결과인데, 왜 이런일이 벌어지는지 확인해 봐야겠다. 원인을 알게 된다면 추가로 포스팅 하겠습니다.

CODE - 시간초과 발생 (함수 사용 ❌)

import sys
read=sys.stdin.readline
n,tree=map(int,read().split())
num=list(map(int,read().split()))
r,l=max(num),0

while l<=r:
    mid=(l+r)//2
    sum_tree=0
    for i in num:
        if i>mid: sum_tree+=(i-mid)
    if sum_tree>tree:
        l=mid+1
        answer=mid
    elif sum_tree==tree:
        answer=mid
        break
    else:
        r=mid-1
print(answer)

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]