Search
Duplicate

예산

주차
16
문제번호
2512
언어
C++
티어
실버
유형
이분탐색
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

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++
복사