BOJ (C/C++) 2805번: 나무 자르기

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

---

풀이

처음엔 내림차순으로 정렬 후 i+1번째 원소와 크기를 비교해가며 구했는데, 나무의 높이가 다 같은 값이면 시간 초과가 발생했다. 이 외에도 여러 반례들이 있어 수정하여 맞추긴 했지만 비효율적이라 알고리즘 분류를 보고 이분 탐색으로 다시 풀어봤다. 
(두 코드 모두 시행 시간은 같음. 그 와중에 효율은 비슷했나봄...)

 

이분탐색으로 배열의 범위를 탐색하는 줄 알아서 알고리즘 분류를 보고도 감이 안 왔는데, 다른 분들의 코드를 보니 절단기의 높이를 탐색하는 거였다. N이 최대 1,000,000개라 전체를 훑으면 시간 초과가 생길 거라 생각했는데 대략 1억 번의 연산이 1초가 걸린다고 하니 100번 내로만 돈다면 시간 제한에 걸리지 않는다.

 

범위가 넓으면 이분탐색을 시도하자!

---

코드 1 - 이분탐색

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> V;

int Get(int N, int M) {
	int min, max, mid, ans;
	long long int total;

	sort(V.begin(), V.end());
	min = 0, max = V[V.size() - 1];

	while (min <= max) {
		total = 0;
		mid = (min + max) / 2;

		for (int i = 0; i < N; i++) {
			if (V[i] > mid) total += V[i] - mid;
		}

		if (total < M)	max = mid - 1;
		else {
			ans = mid;
			min = mid + 1;			
		}
	}
	return ans;
}
int main() {
	int N, M, n;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%d", &n);
		V.push_back(n);
	}

	printf("%d", Get(N, M));
	return 0;
}

 

코드 참고 : https://tooo1.tistory.com/123

---

코드  2 - 내 방식

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> V;

bool cmp(int a, int b) { return a > b; }
int Get_High(int M) {
	long long int high, next = 1, cnt = 1, total = 0;

	sort(V.begin(), V.end(), cmp);
	V.push_back(0);

	high = V[0];
	while (total < M) {

		while (high == V[next]) {
			next++;
			cnt++;
		}

		if (M >= total + (high - V[next])*cnt) {
			total += (high - V[next])*cnt;
			high = V[next];
			next++; cnt++;
		}
		else {
			int m = (M - total) / cnt;
			total += m * cnt;
			high -= m;
			while (total < M) {
				high--;
				if (high < V[next]) {
					cnt++;
					next++;
				}
				total += cnt;
			}
		}

	}
	return high;
}
int main() {
	int N, M, n;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%d", &n);
		V.push_back(n);
	}

	printf("%d", Get_High(M));
	return 0;
}