[백준] 이분 탐색

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

2512번: 예산

이진 탐색(Binary Search) 알고리즘

- 정렬되어 있는 리스트(배열)에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다.

- 반드시 리스트(배열) 내부가 정렬되어 있어야 사용할 수 있습니다.

- left, right, mid(또는 start, end, mid) 3개의 변수를 사용하여 탐색합니다.

- N개의 데이터에 대하여 시간 복잡도는 O(logN) 입니다.

 

해설

- N개의 예산들을 배열에 넣고, sort합니다. (C++의 sort는 quiuck sort로 O(N * log N) 걸림)

- sort한 배열에서 left, right, mid값을 선언하고, 예산 총합에 mid값과 i번째 예산 값중 최소값을 찾아 더해갑니다.

- for i to N 번 실행하여 예산 총합에 값을 더한 뒤, 예산 총합이 M(총 예산)과 비교합니다.

-M보다 작거나 같으면 left + 1을 하고, 상한액 값을 예산 총합으로 바꿔줍니다.

-M보다 크다면 right - 1을 합니다.

-이 과정을 left <= right 일때만 반복합니다.

 

풀이 코드

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

#define FastIO ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

using namespace std;

vector<int> budget;

int main(void)
{
	FastIO;
    
	int N = 0; //지방의 수 및 예산 요청 개수 N
	int M = 0; //총 예산 M

	std::cin >> N;
	for(int i = 0; i < N; i++)
	{
		int input = 0;
		std::cin >> input;
		budget.push_back(input);
	}
	std::cin >> M;

	std::sort(budget.begin(), budget.end());

	int left = 0;
	int right = budget[budget.size() - 1];
	int limitBudget = 0;
	while(left <= right)
	{
		int budgetSum = 0;
		int mid = (left + right) / 2;
		for(int i = 0; i < N; i++)
		{
			budgetSum += std::min(budget[i], mid);
		}

		if(budgetSum <= M)
		{
			limitBudget = mid;
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}

	std::cout << limitBudget << "\n";
	return 0;
}