Search
Duplicate
🙆🏻‍♀️

예산

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

메모리

시간

1116 KB
0 ms

Code

#include <cstdio> #include <algorithm> using namespace std; int main() { int n; int fin, start, mid, end = 0; scanf("%d", &n); int budg[10001]; for (int i = 0; i < n; i++) { scanf("%d", &budg[i]); if (budg[i] > end) end = budg[i]; } int m; scanf("%d", &m); while (start <= end) { fin = 0; mid = (end + start) / 2; for (int i = 0; i < n; i++) { if (budg[i] > mid) fin += mid; else fin += budg[i]; } if (fin <= m) start = mid + 1; else end = mid - 1; } printf("%d", end); return 0; }
C++
복사

문제 풀이

정해진 예산 내에서의 최대값을 구하는 문제이다.
점차 범위를 줄여나가면서 start 와 end를 구해 중간값을 찾고
중간값을 기준으로 만약 각 지역에서 요청하는 값이 더 적다면 해당 값을, 더 크다면 중간값을 더해가며
fin을 구하고 fin을 m과 비교하며 범위를 줄여나간다.
범위가 딱 1개의 값이 될때 end를 출력하여 최대값을 출력해주었다.