문제접근
놓쳤던 부분
•
sum값을 초기화하지 않아서 sum이 계속적으로 누적되는 문제가 있었음
•
start의 부분을 입력받은 값의 최소값으로 설정하게 되면 일부 케이스에 대해서 잘못된 값을 출력하게 됨
→ start를 0으로 시작해야함
→ 최소값으로 설정해서 하는 경우보다 0부터 시작하는게 더 효율적임
코드
9832 KB
176 ms
#include <iostream>
#include <vector>
#include <algorithm>
int n,m;
std::vector<long long> tree;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> n >> m;
tree.resize(n);
for (int i = 0; i < n; i++)
std::cin >> tree[i];
}
void solution()
{
int start;
int end;
int mid;
long long sum;
int result;
start = 0;
end = *std::max_element(tree.begin(), tree.end());
while (start <= end)
{
sum = 0;
mid = (start + end) / 2;
for (int i = 0; i < n; i++)
if (tree[i] - mid > 0)
sum += (tree[i] - mid);
if (sum >= m)
{
start = mid + 1;
result = mid;
}
else
end = mid - 1;
}
std::cout << result;
}
int main(void)
{
input_setting();
input();
solution();
return (0);
}
C++
복사
