백준 2805 나무 자르기 (C++)

2805번: 나무 자르기

이분 탐색으로 분류되어있지만 이분 탐색을 사용하지 않고 문제를 풀었다. 먼저 벡터에 입력값들을 받은 후 오름차순으로 정렬을 해주었다. 그 후 벡터의 맨 마지막 값, 즉 가장 긴 나무의 길이를 따로 저장해준 뒤 반복문을 이 길이를 시작으로 0까지 돌아준다. 반복문을 돌면서 벡터의 마지막 값과 같을 경우 카운트를 해주고 이를 sum에 더해주고 sum이 M보다 크거나 같게 될 경우의 i를 구해 result에 저장하고 이를 출력해주었다. 조건문을 잘못 설정해 시간이 오래 걸린 문제였다. 집중을 하고 풀도록 하자.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long N, M;
vector<long long> tree;
long long result = 0;

void solution() {
	sort(tree.begin(), tree.end());

	long long mm = tree.back();
	long long count = 0;
	long long sum = 0;

	for (long long i = mm; i >= 0; i--) {
		if (sum >= M) {
			result = i;
			break;
		}

		while (!tree.empty()) {
			if (tree.back() != i) break;

			count++;
			tree.pop_back();
		}

		sum += count;
	}

	cout << result;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	long long a;
	for (long long i = 0; i < N; i++) {
		cin >> a;
		tree.push_back(a);
	}

	solution();
	
	return 0;
}