[BOJ / 백준] 2805 나무 자르기 (S2^ / 이분탐색) - Python

링크

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

 

 

 

 

문제 해석

입력

첫 번째 줄 : n m
  n : 나무의 수
  m : 가져갈 나무의 길이
두 번째 줄 : 나무 리스트

 

 

출력

최소한의 나무를 자를 수 있는 절단기의 높이

 

 

 

풀이 & 코드 해석

완전 탐색으로 풀기 위해서는 모든 높이에서 탐색을 해야 하므로 시간초과가 발생합니다.

 

따라서 이분 탐색을 통해 적절한 높이를 찾는 것이 중요합니다.

 

 

20 |               -> 1m
19 |               -> 2m
18 |               -> 3m
17 |        |      -> 5m 
16 |        |      -> 7m
15 |  |     |      -> 10m
14 |  |     |      -> 13m
13 |  |     |      -> 16m
12 |  |     |      -> 19m
11 |  |     |      -> 22m
10 |  |  |  |      -> 26m
================ 9 이하 생략

절단기의 높이는 1번 예시를 통해 보면 이렇습니다.

 

19 미터에서 자르면 그 위에 있는 1m만 가져갈 수 있고, 15m에서 자르면 15m보다 위에 있는 7m를 가져갈 수 있습니다.

 

우리는 문제를 이렇게도 볼 수 있습니다.

 

 

O   O   O   O   O   O   X   X   X   X   X
10  11  12  13  14  15  16  17  18  19  20

절단기 높이를 10m로 한다면 그 위에 있는 22m를 가져갈 수 있으므로 가능합니다. 

 

반면 16m로 한다면 위에 있는 나무가 7m보다 적기 때문에 올바른 높이가 아닙니다.

 

위와 같이 O, X가 특정 구간을 기준으로 나뉘어 있는, 단조성이 있는 경우 이분 탐색을 진행할 수 있습니다. 

 

즉 내가 가져가고자 하는 나무의 높이가 범위 내에 포함되는지를 파악하고 범위를 좁혀나가는 방식을 적용한다면 문제를 해결할 수 있습니다. 

 

 

 

 

코드

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

arr = list(map(int, input().split()))

s = 0
e = max(arr)

tree = 0
ans = -10000000000

while s <= e:
    mid = (s + e) // 2 # 자를 톱 높이

    now_tree = 0
    for i in arr:
        now = i - mid

        # 톱 높이보다 높은 나무라면
        if now > 0:
            now_tree += now

    # 충분한 나무 길이라면
    if now_tree >= m:
        ans = mid
        s = mid + 1

    # 정확히 일치한다면
    elif now_tree == m:
        ans = mid
        break

    # 부족하다면
    else:
        e = mid - 1

print(ans)

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java