코딩 챌린지 15일차 : 2805번 나무 자르기(S2)

2805 : 나무 자르기 - 문제 링크

1. 문제 탐색하기

입력

n 나무의 수
m 집으로 가져가려고 하는 나무의 길이
woods[n] 나무의 높이들

구하고자 하는 것

절단기의 높이의 최댓값

알고리즘 설계

모든 나무에 대해 모든 높이를 브루트포스로 계산하게 된다면
n과 높이가 너무 클 때 시간 초과가 발생하게 된다.

따라서 최저 높이인 0부터 최대 높이인 max(woods) 사이에서 적절한 높이를 찾는
이분 탐색을 진행한다.

우선 가져갈 나무가 적은지 많은지를 알기 위해서는 나무들을 잘라봐야 한다.
나무들을 순회하며 높이만큼 자르고
가져갈 나무가 너무 많다면 높이를 높이고, 가져갈 나무가 부족하다면 높이를 줄여
정답 조건에 맞는 높이를 찾아낸다.

시간복잡도

전체 나무에 대해 $O(N)$
나무의 길이 내에서 이분 탐색$O(logM)$
-> $O(NlogM)$

1 $\leq$ n $\leq$ 1,000,000이고, 1 $\leq$ m $\leq$ 2,000,000,000이므로 약 9,000,000번의 연산 수행 => 통과 가능

2. 코드 설계하기

1. input 받기, 초기값 설정
2. 아래 과정을 통한 이분탐색으로 결과값 도출
1. 나무 잘라보기
2. 가져가는 나무의 양에 따라 low, high값 조정

3. 시도 회차 수정 사항

1회차) 종료 조건을 start < end로 잘못 작성함
2회차) 최종적으로 high값이 설정되었을 때 출력에 -1을 안 해줌
3회차) 성공!

4. 정답 코드

import sys
input = sys.stdin.readline

# input 받기
n,m = map(int,input().split())
woods = list(map(int,input().split()))

# 초깃값 설정
low = 0
high = max(woods)

# 이분탐색
while low <= high:
    # 초깃값 설정
    h = (low + high) // 2
    get = 0

    # 나무 잘라보기
    for wood in woods:
        if wood > h: get += wood - h
        # 가져갈 나무가 너무 많을 때
        if get > m:
            low = h + 1
            break
    else:
        # 딱 맞게 잘라졌을 때
        if get == m:
            print(h)
            break
        # 가져갈 나무가 부족할 때
        else: high = h - 1
else:
    if high == h - 1: print(h - 1)
    else: print(h)

1년 전에 풀었던 문제지만 그때의 내가 작성한 코드가 엉망이라 다시 작성했는데도 분기 조건이라던가 결과값 출력에서 어려움을 겪었다. 이분 탐색은 다시 공부해서 찍어서 맞히지 않도록 해보자!

5. 해설지 참고 후

• 자정 이후 작성