[백준] 2805번 : 나무 자르기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2805번: 나무 자르기

 

1. 문제 설명

2. 풀이과정

해당 문제는 절단기의 높이를 조절하며 잘리는 나무의 길이를 구하여 정답을 도출하는 문제이다.

절단기의 높이는 0부터 자를 나무의 최대 높이 중 하나이다.최대한 빠르게 정답을 도출하기 위해 이진 탐색을 활용하여 절단기 높이를 구하였다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 나무의 수와 가져갈 나무의 길이를 입력받는다. N, M = map(int, sys.stdin.readline().split())
3. 나무들의 높이를 입력받아 리스트로 저장한다. height = list(map(int, sys.stdin.readline().split()))
4. 절단기의 최소 높이를 저장할 변수를 생성하고 초기화한다. low = 0
5. 절단기의 최고 높이를 저장할 변수를 생성하고 나무 높이 중 최댓값을 저장한다. high = max(height)
6. 최소 높이가 최대 높이를 넘어가기 전까지 반복한다. while (low <= high)
7. 최소 높이와 최대 높이의 중간 지점을 구한다. center = (low + high) // 2
8. 나무를 하나씩 가져와 만약 중간 지점보다 길면 자른 나무의 길이를 저장하고 아니면 0을 저장한 리스트를 생성한다. result = [i - center if (i > center) else 0 for i in height]
9. 만약 자른 나무의 길이의 총합이 가져갈 나무의 길이보다 같거나 크면 if (sum(result) >= M)
10. 최소 높이를 중간 지점 다음 높이로 바꾼다. low = center + 1
11. 반면에 자른 나무의 길이의 총합이 가져갈 나무의 길이보다 작으면 else
12. 최대 높이를 중간 지점 이전 높이로 바꾼다. high = center - 1
13. 최소 높이가 최대 높이를 넘어가면 최고 높이를 출력한다. print(high)

반응형

3. 소스코드

import sys

N, M = map(int, sys.stdin.readline().split())
height = list(map(int, sys.stdin.readline().split()))

low = 0
high = max(height)
while (low <= high):
    center = (low + high) // 2

    result = [i - center if (i > center) else 0 for i in height]

    if (sum(result) >= M):
        low = center + 1
    else:
        high = center - 1

print(high)