C++로 주어진 방정식을 만족하는 N개의 양의 정수 찾기

이 문제에서는 세 값 A, B, N이 주어집니다. 우리의 과제는 주어진 방정식들을 만족하는 N개의 양의 정수를 찾는 것입니다.

문제 설명

아래 두 방정식을 동시에 만족하는 N개의 양의 정수를 찾아야 합니다.

x1² + x2² + … + xn² ≥ A
x1 + x2 + … + xn ≤ B

조건을 만족하는 값이 존재하면 해당 N개의 값을 출력하고, 그렇지 않으면 -1을 출력합니다.

입력 예시

N = 4, A = 65, B = 16

출력 예시

1 1 1 8

설명

위 출력이 방정식을 만족하는지 확인해 보면 다음과 같습니다.

1² + 1² + 1² + 8² = 1 + 1 + 1 + 64 = 67 ≥ 65
1 + 1 + 1 + 8 = 11 ≤ 16

즉, 제곱합은 A 이상이면서 전체 합은 B 이하라는 두 조건을 모두 충족합니다.

풀이 접근 방법

가장 간단한 해결책은 제곱합을 최대화하는 것입니다. 핵심 아이디어는 다음과 같습니다.

N-1개의 숫자는 최솟값인 1로 사용하여 전체 합을 최소한으로 유지합니다.
나머지 하나의 숫자를 가능한 한 크게 만들어(예: B - (N-1)) 제곱합을 극대화합니다.

숫자를 제곱하면 값이 급격히 커지므로, 하나의 수에 합의 여유분을 몰아주는 것이 제곱합을 키우는 가장 효율적인 방법입니다. 이렇게 하면 합의 조건(x1 + x2 + … + xn ≤ B)을 지키면서도 제곱합이 A 이상이 될 가능성을 최대로 높일 수 있습니다.

만약 B - (N-1)이 0 이하라면 양의 정수 N개로 합 조건을 만족할 수 없으므로 -1을 출력하고, 계산된 제곱합이 A보다 작은 경우에도 역시 -1을 출력합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

void findNintegers(int N, int A, int B) {
    vector<int> numbers;
    // N-1개의 숫자를 1로 초기화
    for (int i = 0; i < N - 1; i++)
        numbers.push_back(1);
    // 합 조건을 만족할 수 없는 경우
    if (B - (N - 1) <= 0) {
        cout << "-1";
        return;
    }
    // 마지막 숫자에 나머지 합을 모두 할당하여 제곱합 극대화
    numbers.push_back(B - (N - 1));
    // 제곱합 계산
    int vals = 0;
    for (int i = 0; i < N; i++)
        vals += numbers[i] * numbers[i];
    // 제곱합이 A 미만이면 조건 불만족
    if (vals < A) {
        cout << "-1";
        return;
    }
    // 결과 출력
    for (int i = 0; i < N; i++)
        cout << numbers[i] << " ";
}

int main(){
    int N = 4, A = 65, B = 17;
    cout << N << " positive integers that satisfy the given equations are ";
    findNintegers(N, A, B);
    return 0;
}

실행 결과

4 positive integers that satisfy the given equations are 1 1 1 14

복잡도 분석

이 알고리즘은 배열을 한 번 순회하며 제곱합을 계산하므로 시간 복잡도는 O(N), 결과 저장에 O(N) 공간이 필요합니다.