:: ADVANCE ::
[BaekJoon][2805] 나무 자르기 본문
반응형
BAEKJOON ONLINE JUDGE
https://www.acmicpc.net/problem/2805
H 높이를 찾는 이진 탐색을 하면 된다.
H 값을 기준으로 잘린 나무의 합이 필요한 값보다 크면 더 큰 H를 찾아야 하고, 잘린 나무의 길이 합이 M보다 작으면 H는 더 낮아야 한다.
여기서, 문제의 특성을 잘 살펴보면 H 값이 변하면 잘린 나무의 값은 무조건 변하게 된다.
따라서, 잘린 나무의 길이의 합이 M과 같으면 그 H값이 바로 최대값이다.
하지만 여기서 잘린 나무의 길이 합이 딱 M과 같지 않을 수도 있기 때문에
그럴 경우에는 합이 M보다 큰 마지막 경우의 end 값을 출력해 주어야 한다.
(end를 출력하는 이유는 조건을 만족하는 마지막 middle에서 + 1을 한 값이 start가 되고,
계속 범위를 줄여 탐색을 하였을 때 끝나는 값이 start - 1이다. (이것은 직접 손으로 탐색 범위를 계산해 보면 알 수 있다.)
그리고 이 start - 1은 조건을 만족하는 마지막 middle 값이기 때문에 M 이상의 나무를 얻을 수 있는 최대 H이다.)
반응형
'Algorithm > Binary Search' 카테고리의 다른 글
[BaekJoon][1920] 수 찾기 (1) | 2016.09.27 |
---|---|
[BaekJoon][2613] 숫자구슬 (3) | 2016.09.05 |
[BaekJoon][2110] 공유기 설치 (0) | 2016.06.26 |
[BaekJoon][1654] 랜선 자르기 (0) | 2016.06.26 |
[BaekJoon][2343] 기타 레슨 (0) | 2016.06.25 |
Comments