[Softeer] 슈퍼컴퓨터 클러스터
int 뿐만 아니라, long long의 범위 확인도 신경써야 하는
long long을 과신하는 우리에게 경각심을 주는 문제....

#include<iostream>
#include<algorithm>
using namespace std;
int sn[100000];
int main(int argc, char** argv)
{
int N;
long long B;
scanf("%d%lld", &N, &B);
int min_sn = 1100000000;
for(int i = 0; i<N; i++) {
scanf("%d", &sn[i]);
min_sn = min(min_sn, sn[i]);
}
long long low = min_sn;
long long high = 2000000001;
long long ans = -1;
while(low <= high) {
long long tar = (low + high)/2;
long long sum = 0;
for(int i = 0; i<N; i++) {
if(sn[i] < tar) {
long long pow = tar-sn[i];
pow *= pow;
sum += pow;
if(sum > B) break;
}
}
if(sum<=B) {//가능 -> mid 올리기
ans = max(ans, tar);
low = tar + 1;
}
else {//불가능 -> mid 줄이기
high = tar - 1;
}
}
printf("%lld", ans);
return 0;
}
포인트1: sum을 pow 함수를 써서 구해주면 안됨
#include <cmath>
...
sum += pow(tar-sn[i], 2);
...
pow 는 인수들이 뭐로 들어오냐에 따라 리턴값이 다른데
인수로 long double이 들어와야 long double을 리턴하던가 그랬다
인수로 정수를 넣으니까 아마 그냥 double로 처리될 거 같은데
그러면 오버플로가 나서 pow값을 제대로 구하지 못한다
애초에 long long범위까지 간다면 long double도 부족할 것
포인트 2: if(sum>B) break;
-> 단순히 가지치기의 의미가 아니라 이것도 오버플로우를 막기 위함이다
이 문제에서 target(코드에서는 tar)은 이론적으로 최대 10^18까지 가능하다
N의 최대는 10^5 이므로 10^18 * 10^5 가 계산된다고 하면 이는 long long의 최대값도 넘게된다
(long long 최대값은 대략 9*10^8 보다 약간 큼)
(unsigned long long 도 이거보다 두배만 크니까.. 어떤 자료형으로 바꿔도 커버를 못함)
따라서 sum을 계산하는 와중에 long long 최대값을 넘어 오버플로가 생기는 일이 없도록
B를 초과 한 순간 봐줄 필요가 없으므로 for문을 탈출해버리도록 해줘야 한다
개인적으로.. 두번째 포인트가 좀 떠올리기 어려웠던 것 같다
long long으로 두면 우선 안심하고 범위 계산을 안하니까..
이상하게 자꾸 틀리길래 검사해보니까 저 부분이 문제가 될 거 같았다
추가로, tar를 구할 때 오버플로가 걱정되면 tar = low + (high-low)/2 를 해줘도 된다
근데 그냥 long long으로 하는게 편하다 ㅎㅎ