메모리
시간
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를 출력하여 최대값을 출력해주었다.