2805번 : 나무 자르기 - Python

문제

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

풀이

매개 변수 탐색을 이용해서 문제를 풀 수 있다.
처음은 1~'가장 큰 나무의 높이' 의 중앙을 찾고(mid), 절단기를 mid로 설정했을때 나오는 나무들의 길이가 M보다 크다면 mid를 줄여가면서 M에 맞는 최대값을 찾는 방법으로 문제를 풀 수 있다. 만약 나무들의 길이가 M보다 작다면 mid를 늘려야 한다. 조건에 만족하는 수들 중 가장 큰 값을 찾는 문제이다.

코드

from sys import stdin

input = stdin.readline

def find(array, n):

    #초기값을 설정해준다.
    start = 1
    end = max(array)

    while start<=end:
        sum = 0
        mid = (start+end)//2

        for i in array:
            if i>mid: #자를 수 있다면
                sum+= i- mid #잘라서 sum에 더한다.

        if sum>=n:#sum이 조건을 충족한다면
            start = mid+1#좀 더 절단기를 높여서 찾아본다.
        else:#조건에 충족하지 못하면
            end = mid-1#좀 더 절달기를 낮춰서 찾아본다.
    
    #while문을 다 돌고 나면 end는 가장 최적의 값을 가지고 있다. 
    return end #end가 절단기의 최댓값을 가진다.


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

print(find(array,m))

비슷한 문제

1654번 : 랜선 자르기 / 풀이
2110번 : 공유기 설치 / 풀이