[백준] 2805번 - 나무 자르기 (이분 탐색) - 결과 포함

www.acmicpc.net/problem/2805

2805번: 나무 자르기

직전에 풀었던 랜선 자르기 문제와 거의 동일한 문제이다.

문제의 내용이나 숫자는 다르지만

결국 푸는 방식은 같고 중간값으로 나누지 않고 뺀다는 것이 다르다.

 

파라메트릭 서치 유형으로 결정을 하는 방식으로 문제를 해결할 수 있다.

절단기의 최대 높이를 구하는 문제이지만

h 높이로 잘랐을 때 필요한 나무 길이가 나오는 지를 결정하는 문제로 바꾸어 해결할 수 있다.

 

나무를 자를 수 있는 최소, 최대 높이를 정하고 그 안에서 중간값을 반복해서 구하면서 나무의 길이를 비교했다.

문제에 나와있는 테스트케이스도 통과해서 제출했는데

시간 초과가 발생했다.

 

혹시나 하는 마음에 PyPy3로 제출했는데 이번에는 "틀렸습니다"가 결과로 나왔다.

틀렸습니다가 나온 반례는 답이 0인 경우였다.

 

이전의 문제를 생각하면서 풀다보니 0의 경우에 1이 답으로 나오도록 예외 처리를 했던 것이 오답의 원인이었다.

 

하지만 고치고나서도 Python3의 "시간 초과"는 고쳐지지 않았다.

생각한 방법은

기존에는 가지고 있는 나무들이 중간값(mid)보다 큰 경우에만 자르기 위해서 모두 높이를 확인했는데

생각해보니 내림차순으로 나무들을 정렬하면 중간값(mid)보다 작은 나무가 나오면 그 이후에 나무들은 확인하지 않아도 된다는 생각을 했다.

그래서 역으로 정렬한 후 mid 보다 작은 나무가 등장하면 바로 break를 하는 방식으로 수정했지만 여전히 "시간 초과"는 고쳐지지 않았다.

역으로 정렬을 하고나서 뒤에 것들은 보지 않는다는 것은 최악의 경우 오히려 정렬하는 시간만 낭비되고 모든 나무를 보아야할 수도 있다는 것을 이후에 깨달았다.

 

신기한 것은 PyPy3로 제출하면 "정답입니다"가 결과로 나왔다.

그래도 Python3로 푼 사람들이 반드시 존재하기 때문에 나의 코드가 잘못되었다는 것이 분명했다.

질문을 검색해본 결과

 

나무들의 높이를 검사해서 필요한 길이를 구하는 과정을 리스트 내포를 이용했을 때 통과했다.

====>변경 전

for l in data:
	if l > mid:
    	count += l - mid

====>변경 후

count=sum([l-mid if mid < l else 0 for l in data])

리스트 내포(List Comprehension)의 성능에 대해 알아보니 리스트에 대해 일반적인 for문을 돌리는 것보다

성능이 좋다고 한다.

[참고]velog.io/@hj8853/TIL-6-Python

[TIL - 6 / Python] List Comprehension

[소스코드]

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
data = list(map(int, sys.stdin.readline().rstrip().split()))

start = 0
end = max(data)

result = 0
while start <= end:
    count = 0
    mid = (start + end) // 2
    count=sum([l-mid if mid < l else 0 for l in data])

    if count < m:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)