[백준] 2805번 나무 자르기(파라메트릭 서치)(Python - 파이썬)

백준 2805번 문제입니다. (solved.ac)기준 실버 3 문제입니다.

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

2805번: 나무 자르기

첫째 줄에 나무의 수(N)과 상근이가 집으로 가져가려고 하는 나무의 길이(M)을 입력 받는다. 

둘째 줄에는 나무의 높이가 주어진다. 상근이가 집으로 가져가려고하는 나무의 길이(M)만큼  절단기를 이용하여 잘라서 가져가야 하기 때문에 절단기의 높이를 파라메트릭 서치(주어진 범위 내에서 원하는 조건에 가장 일치하는 값을 찾아내는  알고리즘)를 이용하여 접근하는 식으로 문제를 해결하였습니다. 

정답 코드

import sys

# n은 나무의 수 m은 집으로 가져가려고 하는 나무의 길이
n, m = map(int, sys.stdin.readline().rstrip().split())

# 나무의 높이들
wood = list(map(int, sys.stdin.readline().rstrip().split()))

# 이분 탐색을 위하여 오름차순 정렬
wood.sort()

# 최소 절단기의 높이
start = 1
# 최대 절단기의 높이
end = max(wood)
# 결과값을 넣을 변수
result = 0


while start <= end:

    # 잘려진 나무의 길이의 합(total)를 담을 변수
    total = 0

    # 절단기의 높이(mid)
    mid = (start + end) // 2

    # 나무를 하나씩 꺼내어(x) 순차적으로 절단기의 길이(mid)와 비교하여
    # 나무의 길이(x)가 더 길다면 절단기의 길이(mid)만큼 잘라서
    # 잘려진 나무의 길이의 합(total)에 넣음.
    for x in wood :
        if x > mid :
            total += x - mid

    # 잘려진 나무의 길이(total)의 합이 필요한 나무의 길이(m)보다 작다면
    # 나무를 더 많이 잘라야 하므로 절단기의 높이(mid)를 짧게 해야한다.
    # end = mid - 1하여 다음 절단기의 높이(mid)를 줄인 후 다시 탐색
    if total < m :
        end = mid -1
    # 우선 결과 값(result)에 현재 절단기의 높이(mid)를 넣어줌.
    # 탐색을 반복하며 결과 값(result)에 조건에 부합하는 값이 들어가게 됨.
    # 잘려진 나무의 길이(total)의 합이 필요한 나무의 길이(m)보다 크거나 같다면
    # 나무를 덜 잘라야 하므로 절단기의 높이(mid)를 길게 해야한다.
    # start = mid + 1하여 다음 절단기의 높이(mid)를 늘린 후 다시 탐색
    else :
        result = mid
        start = mid + 1

print(result)

비슷한 유형의 문제들

[백준] 2110번 공유기(파라메트릭 서치)(Python)

[백준] 2110번 공유기(파라메트릭 써치)(Python)

[백준] 2512번 예산(파라메트릭 서치)(Python)

[백준] 2512번 예산(파라메트릭 써치)(Python)

[백준] 1654번 랜선 자르기(파라메트릭 서치)(Python)

[백준] 1654번 랜선 자르기(파라메트릭 서치)(Python)