Memo
로직 설명
•
예산의 상한액을 결정하고, 그 값과 예산 요청 값들의 최소값을 모두 더합니다.
•
더한 값이 M보다 작으면 상한액을 올리고, 크거나 같으면 상한액을 내립니다.
•
더한 값이 M이랑 같거나 작아지면 그 값이 정답입니다.
Code
제출 날짜
@4/15/2021
메모리
2056 KB
시간
0 ms
#include <iostream>
#include <algorithm>
int N, M, MAX_, ans;
int request[10001];
void io_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
io_faster();
std::cin >> N;
MAX_ = 0;
for (int i = 0 ; i < N ; i++)
{
std::cin >> request[i];
if (MAX_ < request[i])
MAX_ = request[i];
}
std::cin >> M;
}
void solve()
{
int left = 0, right = MAX_, mid, cnt;
while (left <= right)
{
mid = (left + right) / 2;
cnt = 0;
for(int i = 0 ; i < N ; i++)
cnt += std::min(mid, request[i]);
if (cnt <= M)
left = mid + 1;
else
right = mid - 1;
}
ans = right;
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사