나무 자르기

• Prob
• Solv
• Check
• Ref

나무 자르기

Prob

주어진 나무 수 N
필요한 나무 길이 M
절단기 높이 H
나무를 필요한 만큼만 가져가기 위한 절단기 높이의 최댓값

Solv

나무 tree를 H로 절단해서 모두 더한 길이를 n이라 할 때, n이 M이 되는 값 이분 탐색
low를 0으로 high는 tree의 최댓값으로 설정
n\(>=\)N인 경우 low = H+1
n\(<\)N인 경우 high = H-1
low > high 일때까지 반복

Check

N=4 M=7
tree=[20 15 10 17]

H	low	high	n
10	0	20	22
15	10+1	20	7
18	15+1	20	2
16	15+1	18-1	5
15	16	16-1	7

N=4 M=7
tree=[50 15 10 17]

H	low	high	n
25	0	50	25
38	25+1	50	12
44	38+1	50	6
41	39	44-1	9
42	41+1	43	8
43	42+1	43	7
43	43+1	43	7

Ref