https://www.acmicpc.net/problem/2512
목적
지방예산을 모두 더해서 국가예산에 최대한 가깝게 만들 수 있도록 상한액을 정하라.
접근법
1. 상한액을 1씩 더하거나 빼서 구하려고 하면, 시간초과가 발생하므로 이분 탐색 알고리즘을 이용하여 접근한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,a[10001],ret;
void bs(int l,int r){
if(l>r){
ret=r;
return;
}
int h=(l+r)/2;
long long k=0;
for(int i=0;i<n;++i) k+=(a[i]<h?a[i]:h);
if(k<=m) bs(h+1,r);
else bs(l,h-1);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
int tmp=0;
for(int i=0;i<n;++i){
cin>>a[i];
if(tmp<a[i])tmp=a[i];
}
cin>>m;
bs(0,tmp);
cout<<ret;
}
|
문제 설명과 코드에 대한 피드백은 언제나 환영합니다.
다양한 의견 댓글로 남겨주세요.
'Problem Solving > BOJ 백준' 카테고리의 다른 글
[ BOJ 백준 2842번 - 집배원 한상덕 ] 해설 및 코드 (2) | 2019.12.10 |
---|---|
[ BOJ 백준 1654번 - 랜선 자르기 ] 해설 및 코드 (0) | 2019.12.10 |
[ BOJ 백준 2805번 - 나무 자르기 ] 해설 및 코드 (0) | 2019.12.10 |
[ BOJ 백준 1022번 - 소용돌이 예쁘게 출력하기 ] 해설 및 코드 (0) | 2019.12.10 |
[ BOJ 백준 3005번 - 크로스워드 퍼즐 쳐다보기 ] 해설 및 코드 (0) | 2019.12.09 |