개발일지/Algorithm
백준 - 2805 나무 자르기 [이분 탐색]
E-room
2023. 10. 25. 23:04
728x90
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
1. 문제 요약
나무의 수 n, 가져가려고 하는 나무의 길이 m이 주어지고,
나무의 높이 수열이 주어진다.
자를 높이를 지정하면 해당 높이에 맞게 모든 나무가 잘리며, 지정한 높이 이하의 나무들은 잘리지 않는다.
m을 만족하면서 자를 수 있는 나무의 높이의 최솟값을 구하시오.
2. 접근 방법
- 자르는 높이 별로 얻을 수 있는 나무의 길이를 수열이라 생각하고 이분 탐색을 활용하여 풀면 쉽게 풀 수 있습니다.
- 빨간색이 배열의 인덱스, 파란색이 탐색할 배열이라 생각하고 이분 탐색을 사용합니다.
3. 파이썬
def solution(target, trees):
s = 1
e = max(trees)
while s <= e:
mid = (s+e) // 2
wood = 0
for tree in trees:
if tree > mid:
wood += tree - mid
if wood >= target:
s = mid + 1
else: # wood < target
e = mid - 1
return e
4. 자바
private static int solution(int target, int[] trees) {
int s = 1;
int e = getMaxValue(trees);
while (s <= e) {
int mid = (s + e) / 2;
long wood = 0;
for (int tree : trees) {
if (tree > mid) {
wood += tree - mid;
}
}
if (wood >= target) {
s = mid + 1;
} else {
e = mid - 1;
}
}
return e;
}
5. 전체 코드
728x90