문제 링크

문제 해설이 아닌 풀이하면서 거쳐간 생각들을 기록하는 글입니다.


문제

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다.

성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다.

성원이는 엔토피아가 선물해준 저울 위에 올라갔다. “안돼! G 킬로그램이나 더 쪘어ㅜㅠ”라고 성원이가 말했다. 여기서 말하는 G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.

성원이의 현재 몸무게로 가능한 것을 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 G가 주어진다. G는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우는 제외해야 한다.



접근 과정

  1. 자연수의 집합 중 제곱의 차가 G가 되는 순서쌍을 찾고 그 중 큰 수가 성원이의 현재 몸무게가 된다. 처음엔 어느 범위의 자연수 까지 탐색할지 확인하기 위해 1씩 차이나는 자연수 끼리 제곱차가 G의 최대값이 될 때 까지 계산해보았다. \(n^{2} - (n-1)^{2}\)은 현재 몸무게가 n일 때 가능한 제곱차의 최소값이므로 이 값이 G의 최대 값인 100,000보다 크다면 n 이후의 수는 확인할 필요가 없어진다. 간단한 코드를 통해 확인하였을 때 탐색 해봐야하는 n의 최대 값이 50,000으로 확인되었다.

  2. 모든 순서쌍을 확인하기엔 시간내로 확인이 어려울 것이다. 그래서 현재 몸무게 r과 기존 몸무게 l 순서쌍으로 나타날 수 있는 가장 작은 순서쌍에서 시작하여 제곱차가 G보다 작다면 r을 한 칸 이동시키고, G보다 크다면 l을 한 칸 이동시켜 일치하는 제곱차가 G와 일치하는 순서쌍을 확인하는식으로 탐색 범위를 줄이도록 구현하였다. 구현이 꽤나 단순하므로 투포인터 알고리즘에 대한 이해가 있다면 (혹은 없더라도) 코드에서 알고리즘의 동작을 파악해볼 수 있으 것이다.


소스 코드

#include <iostream>

int main() {
    long long g;
    std::cin >> g;

    long long l = 1;    // 기존 몸무게
    long long r = 2;    // 현재 몸무게
    int cnt = 0;

    while (l < r) {
        long long likeG = r * r - l * l;

        if (likeG == g) {
            std::cout << r << '\n';
            ++l;
            ++r;
            ++cnt;
        } else if (likeG < g) {
            ++r;
        } else {
            ++l;
        }
    }
    
    if (cnt == 0) {
        std::cout << -1;
    }
    return 0;   
}