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

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

# 조건

• 나무 M미터 필요한 상근이
• 목재 절단 높이 H설정
• 높이가 H보다 높은 나무는 H위의 부분 절단 자른 부분을 들고 집에 간다.
• H는 양의 정수 또는 0
• 필요한만큼만 들고 간다고 할 때, M미터의 나무를 집에 가져가기 위한 설정할 수 있는 높이의 최댓값

 

# 접근방법

• 브루트포스로 한다면 시간초과가 발생하기 때문에
• 이분탐색을 활용
• 처음엔 시작, 끝점을 중간값으로 변경해주며 구현하였지만 시간초과
• 또한 잘린 나무의 합을 조건문 컴프리헨션을 통해 시간 단축
• 시작, 끝점을 중간값이 아닌 +1 과 -1로 해주었다.

 

 

# 시간초과 코드

1. 단순 반복문 사용
2. 함수 내부 end, start를 middle값 대입해주며 구현

# 1. 단순 반복문

# 나무의 수, 필요한 길이 M  
N, M = map(int, input().split())  
# 나무의 높이  
tree = list(map(int, input().split()))

longest = max(tree)  
  
# 제일 위에서부터 설정하며 차이가 M과 같다면 출력  
for i in range(longest,-1, -1):  
    result = 0  
    for j in tree:  
        if i<=j:  
            result += j-i  
  
    if result >= M:  
        print(i)  
        break


# ==========================================================================

# 2. start+end로 구현

def saw(H):  
    global start, end  
  
    while start < end:  
        result = 0  
        for i in tree:  
            if i > H:  
                result += i-H  
        if result == M :  
            return H  
        elif result > M:  
            start = H  
            H = (start+end) // 2  
        elif result < M:  
            end = H  
            H = (start+end) // 2  
  
    if start >= end:  
        return H  
# 나무의 수, 필요한 길이 M  
N, M = map(int, input().split())  
# 나무의 높이  
tree = list(map(int, input().split()))  
  
  
start = tree[0]  
end = tree[-1]  
H =(start+end)//2  
print(saw(H))

 

 

# 통과 코드

n,m=map(int,input().split())
L=list(map(int,input().split()))
# 가장 낮은 값과 나무 중 가장 큰 값
down=0
up=max(L)

answer=-1

# 낮은 높이가 up을 넘지 않을 때까지만 반복
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)

 

 

• 같은 이분탐색을 하더라도 이분 탐색 기준을 어떻게 변경 해주냐의 차이가 큰 것 같다.
• 컴프리헨션을 사용하는 것이 시간효율적으로 좋다고 알고 있기 때문에 익숙해지자.
• 재귀로 구하는 방법도 연습하면 좋을 것 같다.