[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으로 하는게 편하다 ㅎㅎ