현재 몸무게 제곱에서 기억하고 있던 몸무게 제곱을 뺀 G가 주어질 때
가능한 현재 몸무게를 구하는 문제입니다.
저는 분류를 수학이라 생각하고 풀었습니다.
몸무게는 자연수이기 때문에 가능한 가장 가벼운 현재 몸무게는 1 + sqrt(G)입니다.
그 미만으로는 기억하는 몸무게가 0이하로 내려가기 때문이죠.
그래서 가장 가벼운 현재 몸무게부터 가능한 가장 무거운 몸무게까지 비교하도록 하겠습니다.
가장 무거운 현재 몸무게는 i2 - (i-1)2이 G보다 크게 되면 제곱 수의 차가 G가 나올 수 없기 때문에
\(i^2 - (i-1)^2\)이 G보다 크기 전이 가장 무거운 현재 몸무게입니다.
이므로 기억하는 몸무게를 구하고
기억하는 몸무게를 제곱 근을 구하고 그 수가 자연수이면 답이 될 수 있습니다.
자연수 판별하는 방법은
제곱 근을 구한 값을 x라고 하겠습니다.
실수 x를 내림을 하여 소수점 자릿수를 버리고
실수(부동 소수점) 오차를 고려하여 비교를 해주시면 됩니다.
실수는 비교할 때 정수처럼 비교 연산자를 사용하면 답이 틀리게 나올 수 있기 때문에
실수 오차 값이 \(10^{-6} \sim 10^{-9}\) 이하 라면 두 실수가 같습니다.
float은 \(10^{-6}\) , double은 \(10^{-15}\) 자리까지 정확성이 높다고 합니다.
가능한 답을 출력해 주시고 가능한 답이 없으면 -1을 출력하면 됩니다.
다른 분들 풀이 보면 투 포인터로 푸신 분들이 많아서
투 포인터를 이용하여 푸셔도 좋을 것 같습니다!!
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define EPS (1e-9)
using namespace std;
int main() {
FIO;
int G, flag = 0;
cin >> G;
for (int i = (int)sqrt(G) + 1; 1ll * i * i - 1ll * (i - 1) * (i - 1) <= G; i++) {
double x = sqrt(1.0 * i * i - G);
if (abs(floor(x) - x) <= EPS) cout << i << '\n', flag = 1;
}
if (!flag) cout << -1 << '\n';
return 0;
}