백준 1484번 다이어트 [C++]

https://www.acmicpc.net/problem/1484

1484번: 다이어트

 

 

#문제 간단 정리

 

#문제 해결 방법

성원이의 현재 몸무게를 x, 기억하고 있는 몸무게를 y라고 할 때, 주어진 조건은 x^2 - y^2 = G입니다. 이 식은 (x + y)(x - y) = G로 변환할 수 있으며, 우리는 x와 y의 모든 가능한 쌍을 찾아야 합니다. 그러나 주어진 조건에 따라 x와 y는 모두 자연수여야 하며, x > y 조건을 만족해야 합니다

 

여기서 자연수임을 확인하는 방법은 구한 y^2 값을 정수형으로 제곱근을 구한후에 다시 제곱을해서 원래값하고 같은지 확인하면 됩니다.

#전체 코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int G;
    cin >> G;

    bool found = false;

    for (int x = 1; x <= 100000; x++) {
        // x^2 - y^2 = G => y^2 = x^2 - G
        long long y2 = (long long)x * x - G;
        // y가 자연수인지 확인
        int y = (int)sqrt(y2);
        if (y > 0 && (long long)y * y == y2) {
            cout << x << '\n';
            found = true;
        }
    }

    if (!found) {
        cout << -1 << '\n';
    }

    return 0;
}