백준2512번 "예산" (Binary_search)

문제

 

 

---------------------- ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- ----------------------

 

문제 접근 순서.

 

1. 어떠한 값의 범위를 두고 그 조건에 맞는 최대값을 찾는 문제이므로 "이진 탐색 (Binary_Search)" 를 생각함.

 

2. 이진탐색으로 했을시  -  1번. 인덱스로 접근할지  ( 수가 연속되지 않을 때 ) 

                                     -  2번. 연속된 수의 범위에서 접근할지  ( 연속되는 수가 가능할 때 )

 

3. 여기서는 예산 삭감에대한 비용이 연속적인 0 ~ 10,000의 값이므로 2번 방법을 선택했다. 

 

이제 코드로 작성해보자면

 

각 도시 개수, 도시에 대한 예산, 한정 예산 등을 입력 받고

해당 예산을 정렬을 진행.

현재 임의로 지정한 mid값을 기준으로 이진 탐색

해당 mid값을 출력.

 

---------------------- ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- ----------------------

 

코드

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

using namespace std; 



int main()
{

	// 범위설정을 그 안에서하기

	int i_inputCityCount = 0;

	cin >> i_inputCityCount; 

	vector<int> m_vec; 


	
	for(int i =0; i<i_inputCityCount; i++)
	{
		int iNeedMoney = 0; 
		cin >> iNeedMoney; 

		m_vec.push_back(iNeedMoney);
	}

	int i_TargetMoney = 0;
	cin >> i_TargetMoney;
	
	sort(m_vec.begin(), m_vec.end());



	int left = 0;
	int right = m_vec[m_vec.size() - 1];
	int mid = (left + right) / 2;

	while(left<=right)
	{
		int sum = 0;

		for(auto& iter : m_vec)
		{
			sum += min(iter, mid);
		}

		if (sum <= i_TargetMoney)
		{
			left = mid + 1;
		}

		else
		{
			right = mid - 1;
		}
		

		mid = (left + right) / 2;
	}


	cout << mid; 

}