[BOJ] 2805번 나무 자르기 / 사용언어 : 파이썬(python)

※ 문제링크 

2805번: 나무 자르기

※ 관련문제

[BOJ] 1654번 랜선 자르기 / 사용언어 : 파이썬(python)

해당문제는 이분탐색과 매개변수탐색을 활용하여 푸는 문제였다. BOJ의 1654문제인 랜선자르기와 거의 유사한 문제로 풀이방법도동일하게 작성해서 문제를 풀었다. 다만 연산을 하는 데 시간이 더 걸려서 Pypy3로만 통과가 가능하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력값을 받고 heap정렬을 통해 받은 값을 정렬해준다.

2. start값과 end값을 설정하고, 해당 값들을 이용해 mid값과 value값을 갱신하여준다.

3. 조건에 부합하는 값이 나올때까지 함수를 반복하여 결과값을 받은 다음,  print문을 활용하여 결과문을 출력해준다.

 

import heapq
N, M = map(int, input().split())
samples = input().split()
samples_ch = []
for sample in samples:
    heapq.heappush(samples_ch, int(sample))
trees = []
for _ in range(N):
    trees.append(heapq.heappop(samples_ch))    
start = 0
end = sum(trees) + 1
value = 0
def check(trees, start, end, M, value):
    length = 0
    mid = int((start + end) / 2)
    for tree in trees:
        length_s = tree - mid
        if length_s > 0:
            length += length_s
            if length >= M:
                break
        else:
            pass
    if length >= M:
        if value == mid:
            return value
        else:
            value = mid
            start = mid
            return check(trees, start, end, M, value)
    else:
        end = mid
        return check(trees, start, end, M, value)
print(check(trees, start, end, M, value))

 

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.