문제접근
•
범위 설정을 하고 그 범위의 중간값으로 계산들을 한 다음 그 결과에 따라 범위를 조정해나가면서 중간값을 찾음
놓쳤던 부분
•
답을 출력하기 위해 또 다른 변수를 사용할 필요 없이 기존의 변수들로 정답을 출력할 수 있다
이 과정에서 start로 출력할지 end로 출력할지에 따라 값을 조정을 해줘야하는데 start로 출력할 경우 start에 mid + 1이 들어가 있는 상태이기 때문에 start - 1 을 해야 우리가 원하는 답을 출력 가능.
end의 경우 end를 그대로 출력해주면 됨.
코드
2176 KB
0 ms
#include <iostream>
#include <vector>
#include <algorithm>
int n, m;
std::vector<int> input_arr;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> n;
input_arr.resize(n);
for (int i = 0; i < n; i++)
std::cin >> input_arr[i];
std::cin >> m;
}
void solution()
{
int start, mid, end;
int sum;
start = 0;
end = *std::max_element(input_arr.begin(), input_arr.end());
while (start <= end)
{
sum = 0;
mid = (start + end) / 2;
int a = input_arr.size();
for (int i = 0; i < a ; i++)
{
if (input_arr[i] - mid > 0)
sum += mid;
else
sum += input_arr[i];
}
if (sum <= m)
start = mid + 1;
else
end = mid - 1;
}
std::cout << end;
}
int main(void)
{
input_setting();
input();
solution();
return (0);
}
C++
복사
