[백준 알고리즘] 2805번: 나무 자르기 (파이썬 / Python)

---

정답 비율 25.559%...

처음에는 단순히 탐색하는 방식에서 탐색 범위를 줄이고 이중반복문을 사용하지 않음으로써 시간을 줄여보고자 했다.

 

(a = 나무 리스트)

1. max(a) - m보다 큰 값만 존재하는 b리스트를 하나 더 생성 (조건을 만족하지 않는 나무들은 개수에 영향을 주지 않으므로)

2. max(a) - m  ~  max(a)+1의 범위만 탐색하며 조건에 맞으면 출력, break

 

결과는 시간초과가 났다,,

 

시간초과 코드

import sys

n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
b = []
for i in range(len(a)):
    if a[i] > (max(a)-m):
        b.append(a[i])

for i in range(max(a)-m,max(a)+1):
    c = sum(b) - i * len(b)
    if c == m:
        print(i)
        break
    elif c < m:
        print(i-1)
        break

 

8번 줄의 새로운 배열에 append하는 과정이 시간을 많이 잡아먹은 것 같다.

(테스트 케이스에서는 답이 잘 나왔지만) 백준에서는 시간 초과라고만 나와서 답이 정확히 맞은건지도 모르겠다.

 

---

 

배열을 전수조사하지 않고 절반씩 범위를 줄여가는 방식의 이분 탐색을 사용하여 해결하였다.

이분 탐색은 O(logN)의 시간복잡도를 가진다.

 

정답 코드

import sys

n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
left = 0
right = max(a)
result = 0

while left <= right:
    count = 0
    mid = (left + right) // 2
    for tree in a:
        if tree > mid:            #해당 나무가 절단기 높이보다 높은 경우에만
            count += (tree - mid)      #해당 나무에서 절단기 높이를 뺀 만큼을 더해줌(잘린 나무의 높이)
            if count >= m:             #추가하는 중에 이미 구할 나무(m)을 초과해버린 경우 break
                break
    if count >= m:                #자를 양보다 많이 자르거나 딱 맞추어 자른 경우
        result = mid                  #result값에 현재 절단기 높이(mid) 할당
        left = mid + 1                #우측으로 범위 축소(절단기를 높여야 함)
    else:                         #자를 양보다 적게 자른 경우 (문제 조건 위배)
        right = mid - 1               #좌측으로 범위 축소(절단기를 낮춰야 함)

print(result)

 

코드 설명은 주석을 보면 될 것 같다.

 

헷갈린 부분

    for tree in a:
        if tree > mid:        
            count += (tree - mid)      
            if count >= m:             #추가하는 중에 이미 구할 나무(m)을 초과해버린 경우 break
                break

4, 5번째 줄의 코드를 추가하기 전에 시간초과가 났다.

나무를 추가하는 도중 count가 m을 도달한 경우, for문을 빠져나오게 한다.

 

---

2805번: 나무 자르기