반응형
728x170
이분탐색 중에서 풀만한 문제다.
조건을 빼먹으면 틀리는 문제..
그래서 나도 틀림..ㅋㅋㅋ
https://www.acmicpc.net/problem/2512
#맞는 풀이
#include <bits/stdc++.h>
using namespace std;
int N;
vector<long long> countryBudget;
long long total;
long long answer;
long long M;
//1.budget은 주어진 예산을 초과해서 분배해서는 안된다.
//2. budget은 상한만큼만 배정되어야 한다.
bool AssignBudget(long long budget){
if(budget >M)return false; //1
long long sum = 0;
for(auto x : countryBudget){
long long now = min(x, budget); //2
sum += now;
}
if(sum <= total){return true;}
else{return false;}
}
long long Search(long long left, long long right){
long long mid = (left + right) / 2;
if(left <= right){
if(AssignBudget(mid)){
answer = max(answer, mid); //해당 값 갱신
return Search(mid+1, right);
}else{
return Search(left, mid-1);
}
}
return left;
}
int main(){
//1. 입력
cin >> N;
for(int i = 0; i<N; i++){
long long x;
cin >> x;
countryBudget.push_back(x);
M = max(M,x);
}
cin >> total;
//2. 연산
Search(0, total);
cout << answer;
return 0;
}
왜 이분탐색을 써야하느냐??
어떠한 숫자를 고르는 것인데 그 범위가 말도 안되니까?
즉, 0~xxxxx까지의 숫자 중 최댓값을 고르시오라는 문제가 나왔는데 범위가 엄청 크다??
-> N이 정말 크다?? 검색 시간을 줄일 방법을 찾아야 한다
-> 과연 결정 범위가 숫자 범위랑 어떤 관계를 가지고 있냐?
-> 음.. 딱 어느 범위 이상이면 false, 그 안이면 true 문제구나..?
-> 이분탐색을 쓸 수 있겠구나
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 12100번, 2048 C++ [CPP] ★★★★ (0) | 2022.05.01 |
---|---|
백준, BOJ, 2110번, 공유기 설치 C++ [CPP] ★★ (2) | 2022.04.10 |
백준, BOJ, 7662번, N번째 큰 수 C++ [CPP] ★★★ (0) | 2022.03.27 |
백준, BOJ, 7662번, 이중 우선순위 큐 C++ [CPP] ★★ (0) | 2022.03.27 |
백준, BOJ, 4358번, 생태학 C++ [CPP] ★★ (0) | 2022.03.26 |