백준 2805. 나무 자르기[성공]

1.문제 해결 전략

랜선 자르기와 유사한 문제였다. 다만, 조금 운이 좋아서 맞은 것 같다. 결과를 지정하지 않고 단순히 예시 입력값을 통해 right를 출력해보고 그냥 제출했는데 정답이었다. 정확한 방법은 result = max(mid,result)를 이용해서 최대값을 계속 설정해 주어야 한다.

 

2.작성 코드

#include <iostream>
#include <algorithm>
using namespace std;
long long int arr[1000001];
long long int N, M;
bool checking(int num) {
	long long int sum = 0;
	for (long long i = 0; i < N; i++) {
		if (arr[i] - num > 0)
			sum += (arr[i] - num);
	}

	if (sum >= M)return true;
	return false;
}

int main() {
	cin >> N >> M;

	for (long long int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + N);
	long long int left = 1;
	long long int right = arr[N - 1];
	long long int mid = 0;
    // long long result = 0;
	while (left <= right) {
		mid = (left + right) / 2;

		if (checking(mid)) {
			left = mid + 1;
            // result = std::max(mid,result);
		}
		else {
			right = mid - 1;
		}
	}
	cout << right << endl;
}

3.걸린 시간 & 느낀점

개인적인 생각이다. 문제가 시간초과 날 정도로 큰 수의 값에 대해 비교연산을 요할 때 이분 탐색을 사용하는 것 같다. 알고리즘 시간에 배웠던 Promising(유망한 조건)을 설정하기만 하면 나머지는 이분 탐색의 간단한 알고리즘을 적용시키는 것 뿐이다. 효율좋은 탐색 알고리즘이라고 생각하면 문제를 통해 해결방법을 유추하기 쉬울 것이다.