이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 79 번째 글 입니다.
목차
실버3 : 이진 탐색 문제이다.
풀이
예산 금액은 최대예산과 아예 안주는(0원) 방법이 있다. 따라서 0과 max금액을 양 끝으로 잡는다.
left | right | mid | 예산소모금액 | 후보가능여부 |
0 | 150 | 75 | 300 | O |
75 | 150 | 112 | 446 | O |
113 | 150 | 131 | 492 | X |
113 | 130 | 121 | 472 | O |
122 | 130 | 126 | 482 | O |
126 | 129 | 127 | 484 | O |
128 | 129 | 128 | 486 | X |
mid가 m보다 작으면 답의 후보라는 것을 알 수 있다. 탐색은 하되, 답인 상황만 잘 가져오면 됨.
Code
//
// main.cpp
// algorithm_prac
//
// Created by 최완식 on 2021/04/05.
//
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
int req[10001];
bool comp(int a, int b){
return a<b;
}
int main(){
int n, total = 0;
ll m = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> req[i];
total += req[i];
}
cin >> m;
sort(req, req+n, comp);
if (total < m) {
cout << req[n-1] << '\n';
return 0;
}
int left = 0, right = req[n-1];
int ans = 0;
while (left <= right) {
int mid = (left+right)/2;
ll sum = 0;
for (int i = 0; i < n; i++) {
if (mid < req[i]) sum += mid;
else sum += req[i];
}
if (sum > m) {
right = mid-1;
} else {
ans = mid;
left = mid+1;
}
}
cout << ans << '\n';
return 0;
}