나무 자르기(BOJ : 2805)
백준 2805번 : 나무 자르기
본문
제한
문제
상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.
목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.
상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.
출력
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
예제 입력 1
4 7
20 15 10 17
예제 출력 1
15
예제 입력 2
5 20
4 42 40 26 46
예제 출력 2
36
풀이
먼저, 입력받은 나무들의 길이 배열을 tree, i번째 나무의 길이를 tree[i], 절단기에 설정할 높이를 h라고 하자.
i번째 나무는 h보다 높아서 잘릴 수도, h와 같거나 낮아서 잘리지 않을 수도 있다. 잘릴 때에만 총 합에 포함해야 한다.
또한, 나무가 N개이므로 나무가 잘렸는지 판단하여 총합에 포함하는 과정을 N번 반복해야 한다.
이를 코드로 나타내면 다음과 같다.
long sum = 0;
for (int i = 0; i < N; i++) {
if (tree[i] > h) { // 나무가 h보다 클 경우에만 자름.
sum += (tree[i] - h);
}
}
코드를 확인해보면 잘린 나무의 길이의 총 합을 구하는 시간복잡도는 나무의 길이를 판단해서 총 합에 더하는 과정을 N번 반복하기 때문에 O(N)이다.
문제의 시간 제한은 1초로 약 100,000,000번의 연산 이내에 적절한 높이 h를 찾아야 한다.
N의 최댓값은 1,000,000으로, 적절한 h를 구하는 과정이 100번 이내에 이루어져야 시간 제한 조건을 만족할 수 있다.
나무 높이를 K라고 할 때, 순차 탐색으로 h를 찾게되면 시간 복잡도는 O(K) [1 <= K <= 20억]이기 때문에 최악의 경우에 시간 제한 조건을 만족할 수 없다.
따라서 우리는 O(log K)의 시간복잡도를 갖는 알고리즘을 통해 이를 해결해야 한다(K가 20억일 때, O(log K)는 약 31이다).
우리는 이진 탐색 알고리즘을 통해 이 문제를 해결할 수 있다.
이진 탐색 알고리즘은 O(log K)의 시간 복잡도를 가진다.
따라서 이진 탐색 알고리즘을 활용하여 적절한 h를 찾도록하고, 이 과정에서 찾은 h에 대해 나무 배열을 순회하도록 하면, 이 알고리즘은 O(N log K) [N : 나무의 개수, K : 가장 큰 나무의 높이]의 시간복잡도를 가져, 최악의 경우에도 문제의 시간 제한 조건을 만족할 수 있다.
입력받은 나무의 최대 높이를 기준으로 탐색 범위를 절반씩 줄여가면 적절한 h를 찾을 수 있다.
예제 1번을 통해 확인해보자.
나무는 4개로 각각 20, 15, 10, 17의 높이를 갖는다.
필요한 나무 길이는 7이다.
나무의 최대 높이는 20으로, 20의 절반 값인 10을 h로 설정해보자.
h를 10으로 하여 얻은 나무들의 길이는 각각 10, 5, 0, 7로 22 길이의 나무를 얻었다.
우리는 길이 7의 나무가 필요한데 너무 많은 나무를 얻었다. 높이 h를 높여보자
h를 높여주기 위해 최솟값을 올려주겠다. (기존에는 최솟값을 설정하지 않았는데, 이는 0으로 설정한 것과 같은 결과이다)
최솟값을 mid + 1인 11로 설정하고 나무의 최댓값(20)과 최솟값(11)의 중간값(15)로 h를 설정하고 나무를 잘라보자.
잘린 나무들의 길이는 5, 0, 0, 2로 총 길이 7의 나무를 얻을 수 있다.
이는 우리가 필요한 m값과 같다.
적절한 절단기의 높이 h를 찾는 알고리즘을 다음과 같이 설계했다.
max와 min 변수를 초기화한다.
max는 입력받은 가장 큰 나무의 높이, min은 0으로 초기화한다.
min < max인 경우, 아래 내용을 반복한다.
h 변수에 (min + max) / 2를 담는다.h 변수를 통해 잘린 나무들의 길이 합(sum)을 구한다.- 조건에 따라 아래 내용을 수행한다.
sum < m이면 max 변수를 h 값으로 교체한다(h 값을 줄여서 sum 값을 증가시켜야 하기 때문).- 그렇지 않으면
min 변수를 h + 1 값으로 교체한다(h 값을 높여서 sum 값을 감소시켜야 하기 때문).
min 변수에서 1을 뺀 값을 출력한다.
이를 코드로 작성하면 아래와 같다.
public class BOJ2805 {
private static int n;
private static int m;
private static long[] tree;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// n, m 입력받기. n : 나무의 수, m : 필요한 나무 길이
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
tree = new long[n];
m = Integer.parseInt(st.nextToken());
// 나무들의 길이 입력받기
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
long a = Long.parseLong(st.nextToken());
tree[i] = a;
}
Arrays.sort(tree);
long min = 0;
long max = tree[n-1];
while (min < max) {
long mid = (min + max) / 2;
long sum = cutSum(mid);
if (m > sum) {
max = mid;
} else {
min = mid + 1;
}
}
System.out.println(min - 1);
}
// 전체 나무 자른 뒤 남은 길이 합
private static long cutSum(long h) {
long sum = 0;
for (int i = n-1; i >= 0; i--) {
// 정렬된 tree 배열이기 때문에 tree[i]가 높이 h보다 작으면 그 이전 나무들은 모두 h보다 작거나 같다.
// 계산하지 않아도 됨. 반복문 종료.
long afterCut = tree[i] - h;
if (afterCut <= 0) {
break;
}
sum += afterCut;
}
return sum;
}
}