최근 풀이 241101
업그레이드 할 점.
-
문제점.
: 원하는 중간값을 구한 후에, 모든 컨테이너에서 한번에 반복문 돌려서 처리하는 과정을 거침.
-> 정답률 66퍼센트 나왔음.
-
해결책
: 정답 구할때 for문은 돌리지 않는 방법으로 풀었더니 100점 맞음.파의 개수가 100만 개임.
-마지막 result계산하는 부분에서 반복문 돌리면 또 100만이 추가되는 것임.
-처음 파의 길이를 입력하는 부분에서 총합을 구하고,
-계산하는 부분에서 머리를 잘 돌려서 처리하면 시간복잡도 100만은
절약 할 수 있음.
코드
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>
long long s, c;
bool binarySearch(vector<long long>&v , long long target)
{
long long cnt = 0;
for (int i = 0; i < v.size(); ++i)
{
cnt += v[i] / target;
}
//c에 맞춰지는 순간 끝나야 함.
// c보다 cnt값이 작다는 것은, 타겟값이 높아서 그런것이므로
// 타겟값을 낮춰야 함.
return c > cnt;
}
// pm 7:20 ~ 7:47 : 62퍼센트에서 틀림...
int main()
{
cin >> s >> c;
vector<long long>v(s);
// 일단 수가 어마어마하다.
// logN을 가지고 오는 이분탐색을 사용해야 함.
long long sum = 0;
for (long long i = 0; i < s; ++i)
{
cin >> v[i];
sum += v[i];
}
// 파를 최대한 많이
// 어떤 특정값을 골라서. 각 벡터에서나 몫과 나머지 값을 구함.
// 몫으로 구한 것이 c값돠 일치하는 순간에
// 최대값을 구하라는 것임.
long long start = 1;
long long end = *max_element(v.begin(), v.end());
// 440 350 230 // 790 230 // 1020
long long temp = 0;
while (start <= end)
{
long long half = (start + end) / 2;
// 파닭 5개를 못만드는 경우.
// 파의 값을 낮춰야 함.
if (binarySearch(v, half))
{
end = half - 1;
}
else
{
start = half + 1;
}
}
//cout << start << " " << end << " " << (start + end) / 2 << endl;
//long long mid = (start + end) / 2;
//long long res = 0;
//for (auto iter : v)
//{
// res += iter % mid;
//}
cout << sum - (start + end) / 2 * c;
}
중요한 점.
- 반환값을 어떻게 처리할 것인가???
: 등호냐? 부등호만으로 처리할 것이냐?
c : 5일 때
440 350 230 에서 230으로 나누었을 때
1 1 1 -> 3개 밖에 안되므로. 이 때는
cnt와 c가 동일해야 만 하므로,
end를 mid - 1 로 만들어 주는 방식으로 진행하자.
조건 처리
cnt 와 c가 동일한 순간이 의미하는 것은 위에서 계속 end를
줄여 나가고 있다는 것을 의미함.
그래서 cnt < c; 로 해야 함.
왜 cnt <= c; 를 하면 안되는지에 대한 근복적인 이유?
등호를 붙이는 순간. 구하려는 mid 값이 작아지므로, 최대값을 구할 수 없음.
반례에 대해 생각해보면,
174로 파를 나누어 보면, 440 350 230 -> 2 2 1 이됨.
cnt <= c가 되면, 더더 res값이 작아지는 것은 분명한일!
따라서 cnt < c 에서만 동작되도록 해야 함.
그러다가 = 이 되는 순간에 false가 되면서 start 가 커지데 되고,
반복문이 끝마침!
🔥🔥🔥