[백준-파이썬] 2805번: 나무 자르기

백준 2805번 문제

문제 풀이

이분 탐색을 활용해서 풀었다.

1.나무 자르는 위치가 가장 낮을 때(0) 값을 down으로, 가장 높을 때(가장 높은 나무의 높이) 값을 up으로 함.
(처음에는 나무 자르는 위치가 가장 낮을 때를 가장 작은 나무 높이로 했는데, 그게 아니었다!)
2. mid를 up, down을 더하고 2로 나눈 몫으로 함. 이 위치에서 나무들을 자를 경우에 잘린 나무들의 합을 구함.
3-1. 잘린 나무들의 합이 필요한 나무 길이와 일치하는 경우: answer에 mid를 대입하고 break하기
3-2. 필요한 나무 길이보다 많은 경우: 이게 정답이 될 수도 있는 것이니까(3-1이 안될 경우에) answer에 mid를 대입함. 그리고 down을 mid+1로 바꿔서 2로 돌아감.
3-3. 필요한 나무 길이보다 적은 경우: 이건 확실히 정답이 될 수 없으니까 answer에 mid 대입하지 않음. 그리고 up을 mid-1으로 해서 2로 돌아감.

2~3 과정은 down이 up보다 같거나 작을 동안 반복함.

4.마지막에 answer을 출력함

코드

처음에는 이런 코드를 짰는데, 시간 초과가 나왔다.

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

down=0
up=max(L)

answer=-1

while down<=up:
    mid=(down+up)//2
    tree_total=0
    for i in L:
        if (i-mid)>0: #나무 잘린 게 있을 때
            tree_total+=(i-mid)  #잘린 나무의 합

    if tree_total==m: #잘린 나무의 합이 필요한 것과 일치하면 끝
        answer=mid
        break
    elif tree_total>m: #잘린 나무의 합이 필요한 것보다 많으면
        answer=mid
        down = mid + 1

    elif tree_total<m: #잘린 나무의 합이 필요한 것보다 적으면
        up = mid - 1

print(answer)

그러다가 다른 분들의 질문, 답변을 보고서 수정했더니 통과했다.

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

down=0
up=max(L)

answer=-1

while down<=up:
    mid=(down+up)//2
    tree_total=sum((i-mid) if (i-mid)>0 else 0 for i in L)

    if tree_total==m: #잘린 나무의 합이 필요한 것과 일치하면 끝
        answer=mid
        break
    elif tree_total>m: #잘린 나무의 합이 필요한 것보다 많으면
        answer=mid
        down = mid + 1

    elif tree_total<m: #잘린 나무의 합이 필요한 것보다 적으면
        up = mid - 1

print(answer)

바뀐 것은

for i in L:
        if (i-mid)>0: #나무 잘린 게 있을 때
            tree_total+=(i-mid)  #잘린 나무의 합

이 부분을

    tree_total=sum((i-mid) if (i-mid)>0 else 0 for i in L)

이렇게 바꿔준 것이다.

후기

왜 이렇게 바꾼 것이 더 빠른지는 아직 정확히는 잘 모르겠다.. 대충 느낌..만 알겠다....ㅠㅠ
시간 복잡도... 공부하고 싶은데 뭘로 공부해야 할지 모르겠다.
앞으로 더 공부하고, 나중에 추가하려고 한다!