<BOJ 2508> 나무 자르기

문제 링크 icpc.me/2508

이 문제는 높이가 서로 다른 나무 N 그루에서 나무를 M 미터만큼 벌목하고자 하는 문제이다.

벌목기를 사용하려고 하는데, 벌목기의 높이 H 를 지정할 수 있고 H 보다 더 큰 나무를 모두 절단해

각 나무의 높이 - H 만큼의 나무를 얻을 수 있다.

이 때 M 미터만큼 벌목을 하기 위해서 H 를 얼마로 설정해야 하는가를 찾는 문제이다.

처음 접근 방식은 N 그루의 나무 중 가장 높이가 큰 나무의 높이로부터 H 를 순차적으로 찾는 방식이었다.

이렇게 할 경우 간단한 문제는 해결이 가능하지만 나무의 개수가 많아질수록 시간이 오래 걸려 시간 초과가 발생하였다.

// 순차 탐색 

#include <stdio.h>

#include <stdlib.h>

int main() {

int tree, obj;

int *tree_height;

int max_height;

int total;

int prev;

scanf("%d %d", &tree, &obj);

tree_height = calloc(sizeof(int), tree);

for (int i = 0; i < tree; i++) {

scanf("%d", tree_height + i);

}

max_height = tree_height[0];

prev = -1;

while (1) {

total = 0;

for (int i = 0; i < tree; i++) {

if (tree_height[i] - max_height > 0)

total += tree_height[i] - max_height;

}

if (total > obj) {

if (prev < obj && prev != -1)

break;

else max_height++;

}

else if (total < obj) {

if (prev > obj && prev != -1)

break;

else max_height--;

}

else {

break;

}

prev = total;

}

printf("%d\n", max_height);

}

시간 초과가 발생한 후 다음으로 시도한 방법은 나무를 높이 순으로 정렬한 후 순차탐색을 하는 것이었다.

이렇게 할 경우, 마찬가지로 벌목기의 높이 H 를 줄여가며 확인을 해야 하지만 나무가 높이 순으로 정렬되어 있기 때문에

벌목기가 나무보다 높아질 경우 그 뒤의 나무는 자를 수 있는 지를 확인할 필요가 없다.

// 정렬 후 순차탐색

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool comp(int a, int b) {

return a > b;

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

vector<int> v;

int n, m, input;

cin >> n >> m;

for (int i = 0; i < n; i++) {

cin >> input;

v.push_back(input);

}

sort(v.begin(), v.end(), &comp);

int max = v[0];

int sum;

while (1) {

sum = 0;

for (int i = 0; i < n; i++) {

if (v[i] <= max)

break;

sum += v[i] - max;

}

if (sum >= m)

break;

max--;

}

cout << max << "\n";

}

두번째 소스 코드 또한 마찬가지로 시간 초과가 발생했다.

아무래도 H 를 바꿔가며 나무를 일일히 확인하는 방법은 시간적으로 많이 소모된다고 생각이 들었다. 그래서 생각해낸 방법이

두번째 방법과 유사하지만 나무를 확인하는 횟수를 줄이는 것이었다.

간단하게 설명하자면, 위의 소스코드는 H 를 변경할 때마다 모든 나무에서 몇 m 씩만큼의 나무를 얻을 수 있는 지를 계산해야 한다.

하지만 이 과정은 나무가 높이 순으로 정렬되어 있기 때문에 불필요한 과정이었다.

이전 단계 (즉, 이전 벌목기의 높이 H) 에서 벌목 가능한 나무를 X 그루라고 하면, 단계가 변할 때마다 총 얻을 수 있는 나무의 양은 X 만큼

증가하게 된다.

추가적으로 H 가 감소했으니, 이전 단계에서 벌목 가능한 나무의 위치 바로 다음 위치부터 있는 나무만을 확인하면 된다.

이렇게 작성한 소스 코드는 다음과 같다.

// 정렬 후 순차 탐색

// 이전 단계의 탐색 위치를 저장

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

bool comp(long long a, long long b) {

return a > b;

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

vector<long long> v;

long long n, m, input;

cin >> n >> m;

for (int i = 0; i < n; i++) {

cin >> input;

v.push_back(input);

}

sort(v.begin(), v.end(), &comp);

long long max = v[0];

long long sum = 0;

long long index = 0;

while (1) {

sum += index; // sum 을 단계 별로 초기화하지 않고 기존의 값에 H 가 변화함에 따라 추가되는 나무를 더해준다.

for (int i = index; i < n; i++) {

if (v[i] <= max) {

index = i;

break;

}

sum += v[i] - max;

}

if (sum >= m)

break;

max--;

}

cout << max << "\n";

}

이렇게 풀었을 때, 더이상 시간초과는 발생하지 않았지만 왠지 모르게 입력되는 값이 커질수록 결과값이 이상하게 출력되었다.

처음에 long long 을 사용하지 않고 int 형을 사용해 자료형 문제로 생각하고 long long 으로 바꾼 후 다시 제출을 했지만

마찬가지로 36% 정도에서 틀렸다는 결과가 발생했다.

그래서 예외 상황이 생길 수 있나 생각했는데 상황을 찾지 못해 결국 풀이 방식을 바꾸는 쪽을 생각했다.

데이터를 정렬하지 않고 문제를 푸는 방법을 생각하게 되었고, 정렬을 하지 않게 되면 이 알고리즘에서 시간을 줄일 수 있는 방법이

H 의 값을 변경하는 횟수를 줄이는 것이었다.

이 알고리즘의 속도는 H 를 얼마나 많이 변경하느냐와 H 에 따라 벌목할 수 있는 나무를 얼마나 탐색하느냐 이 두 가지에 따라 결정된다.

즉, O(H * N) 이 된다고 볼 수 있다. 이 때, N 을 줄이는 것은 앞서 시도한 방법들에서 실패했으니 H 를 줄이는 방법을 생각해 보았다.

H 를 줄이는 방법은 H 를 N 그루의 나무 중 최대 높이부터 1씩 감소시켜 나가는 것이 아니라 최대 높이와 최소 높이를 기준으로

이분 탐색을 하는 방법이었다.

이분 탐색을 함으로써 O(H * N) 은 O(logH * N) 으로 바꿀 수 있게 되고, H 는 최대 1,000,000,000 의 값을 갖는다고 문제의 조건으로

주어졌으니 log(1,000,000,000) ≒ 29 로 알고리즘의 성능은 O(N) 으로 표현할 수 있게 된다.

소스 코드는 다음과 같다.

// 이분 탐색

#include <iostream>

#define _MAX(A, B) A > B ? A : B

using namespace std;

long long arr[1000001];

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

long long n, m, max = 0;

cin >> n >> m;

for (long long i = 0; i < n; i++) {

cin >> arr[i];

max = _MAX(max, arr[i]);

}

long long low = 0, mid, high = max;

long long sum = 0;

while (low < high) {

sum = 0;

mid = (high + low + 1) / 2;

for (long long i = 0; i < n; i++) {

sum += _MAX(0, arr[i] - mid);

}

if (sum < m) high = mid - 1;

else low = mid;

}

cout << low << "\n";

}