[BOJ 25399 // C++] 라그랑주님 수학에는 뺄셈도 있어요

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25399번 문제인 라그랑주님 수학에는 뺄셈도 있어요이다.
문제는 아래 링크를 확인하자.

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

25399번: 라그랑주님 수학에는 뺄셈도 있어요

음의 정수의 경우 양의 정수를 구성하는 방법에서 부호를 바꿔 답을 구할 수 있으므로 양의 정수들을 제곱수로 구성하는 방법을 알아보자.

 

먼저 주어진 수 \(N\)이 한 개의 제곱수의 합으로 나타날 수 있는지를 확인하자. 이는 주어진 수가 제곱수인지를 확인하는 것과 같다.

 

다음으로 주어진 수가 두 개의 제곱수의 합(또는 차)으로 나타날 수 있는지를 확인하자.

주어진 수가 두 개의 제곱수의 합으로 나타낼 수 있는지의 여부는 투포인터를 이용해 \(O(\sqrt{N})\)에 구할 수 있다.

모든 3 이상의 홀수의 경우 \((n+1)^2-n^2=2n+1\)로부터 두 제곱수의 차로 구할 수 있음을 알 수 있다.

4의 배수의 경우 \((2n+1)^2-(2n-1)^2=4n\)로부터 두 제곱수의 차로 구할 수 있음을 알 수 있다.

그 외의 경우(짝수이지만 4의 배수가 아닌 경우)는 두 제곱수의 차로는 구할 수 없다. 모든 제곱수는 \(4n\) 또는 \(4n+1\)꼴임을 상기하자.

 

남은 수는 두 제곱수의 합으로 나타낼 수 없는, 4의 배수가 아닌 짝수이다.이 경우 아무 홀수 제곱수를 먼저 더한 다음 그렇게 만들어진 홀수를 두 제곱수의 차로 나타내는 것으로 세 정수를 이용해 표현할 수 있다. 이 과정에서, 먼저 더한 홀수 제곱수를 다른 두 수를 찾을 때 재사용하지 않도록 유의하자.

 

마지막으로 0을 1개 이상의 제곱수들로 구성해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll N; bool neg;
vector<ll> vec;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    
    if (N == 0) {
        cout << 3 << '\n' << "+ 5\n- 4\n- 3";
        return 0;
    }
    if (N == 2) {
        cout << 3 << '\n' << "+ 11\n+ 5\n- 12";
        return 0;
    }
    if (N == -2) {
        cout << 3 << '\n' << "- 11\n- 5\n+ 12";
        return 0;
    }
    
    if (N < 0) N *= -1, neg = 1;
    
    
    
    for (ll i = 1; i * i <= N; i++) {
        if (i * i == N) {
            if (neg) cout << 1 << '\n' << '-' << ' ' << i;
            else cout << 1 << '\n' << '+' << ' ' << i;
            return 0;
        }
        
        vec.emplace_back(i * i);
    }
    
    int L = 0, R = vec.size() - 1;
    while (L < R) {
        ll val = vec[L] + vec[R];
        if (val == N) {
            if (neg) cout << 2 << '\n' << '-' << ' ' << L + 1 << '\n' << '-' << ' ' << R + 1;
            else cout << 2 << '\n' << '+' << ' ' << L + 1 << '\n' << '+' << ' ' << R + 1;
            return 0;
        }
        
        if (val < N) L++;
        else R--;
    }
    
    if (N & 1) {
        ll x = N / 2 + 1, y = N / 2;
        if (neg) cout << 2 << '\n' << '-' << ' ' << x << '\n' << '+' << ' ' << y;
        else cout << 2 << '\n' << '+' << ' ' << x << '\n' << '-' << ' ' << y;
    }
    else if (N % 4 == 0){
        ll x = N / 4 + 1, y = N / 4 - 1;
        if (neg) cout << 2 << '\n' << '-' << ' ' << x << '\n' << '+' << ' ' << y;
        else cout << 2 << '\n' << '+' << ' ' << x << '\n' << '-' << ' ' << y;
    }
    else {
        N++;
        ll x = N / 2 + 1, y = N / 2;
        if (neg) cout << 3 << '\n' << '-' << ' ' << x << '\n' << '+' << ' ' << y << '\n' << '+' << ' ' << 1;
        else cout << 3 << '\n' << '+' << ' ' << x << '\n' << '-' << ' ' << y << '\n' << '-' << ' ' << 1;
    }
}