[항해]알고리즘 스터디(백준 #2805)

백준#2805

바로가기

문제 해석
==(입력값) 나무의 수(N), 필요한 나무의 길이(M), 나무들의 높이(tree), 절단기의 높이(H)
==(해석)
상근이는 나무가 M미터 필요하다. 절단기로 나무를 잘라야 한다. 절단기는 작동하기 시작하면 N개의 나무를 수평으로 자른다. 즉, 높이가 각각 tree인 N개의 나무를 H높이에서 절단해 M만큼의 목재를 얻는다.
예를들면 아래 그림과 같다.

수를 대입하는 예시를 든다. 최초에 나무는 4그루 있고, 7M의 목재를 원한다. 나무의 길이는 각각 20, 15, 10, 17이다. 절단기를 몇미터에서 작동시켜야 딱 7M를 얻을 수 있는가를 구해야 한다!

문제 접근
1. 최초에 N과 M을 입력하고, tree를 입력받으면 최종적으로 H가 출력되어야 한다.
2. N과 M 사이에 빈칸을 둔다 == map(int, input().split(" "))을 이용한다.
3. 이분탐색(Binary Search)를 활용한다.

코드

import sys
1	# 나무의 수, 원하는 나무의 길이
2	n, m = map(int, sys.stdin.readline().split())
3	# 나무의 높이
4	tree = list(map(int, sys.stdin.readline().split())
5	
6	# 목재절단기의 높이, 이분 탐색에 사용할 start와 end(left, right로도 많이 쓰임)
7	h = 0
8	start = 0
9	end = max(tree)
10	
11	# start가 더 커지면 (이분 탐색이 끝나면) 반복문을 종료한다.
12	while start<=end:
13	    # 자른 나무의 총 길이
14	    s = 0
15	    # 임의로 설정한 절단기 높이
16	    middle = (start + end) // 2
17	
18	    # 임의로 설정한 높이로 나무를 자른다.
19	    s = sum(i-middle if i > middle else 0 for i in tree)
20	
21	    # 총 나무의 길이가 원하는 나무의 길이보다 길거나 같다면
22	    if s >= m:
23	        # 높이를 설정해주고 탐색을 반복한다. (*)
24	        h = middle
25	        start = middle + 1
26	    # 원하는 나무의 길이보다 짧으면 다시 높이를 탐색한다.
27	    else:
28	        end = middle - 1
29	print(h)