C++로 합과 곱의 차이가 D가 되는 N개의 정수 찾기

문제 개요

두 정수 N과 D가 주어졌을 때, N개의 정수로 이루어진 집합을 찾아야 합니다. 단, 이 정수들의 곱에서 합을 뺀 값이 정확히 D와 일치해야 합니다.

예를 들어 N = 3, D = 5라고 가정해 보겠습니다. 이때 출력은 1, 2, 8이 됩니다.

• 합: 1 + 2 + 8 = 11
• 곱: 1 × 2 × 8 = 16
• 차이: 16 − 11 = 5 ✓

해결 아이디어

이 문제는 복잡한 탐색 없이도 간단한 수학적 트릭으로 해결할 수 있습니다. 바로 다음과 같은 구성을 사용하는 것입니다.

• (N − 2)개의 1
• 하나의 2
• 마지막 하나의 N + D

이 구성에서 합, 곱, 그리고 차이는 각각 다음과 같이 계산됩니다.

• 합 = (N − 2) × 1 + 2 + (N + D) = 2N + D
• 곱 = (N − 2)개의 1 × 2 × (N + D) = 2N + 2D
• 차이 = (2N + 2D) − (2N + D) = D

즉, 어떤 N과 D가 입력되더라도 이 공식에 따르면 곱과 합의 차이가 항상 정확히 D가 됩니다.

C++ 구현 예제

#include<iostream>
using namespace std;

void getNNumbers(int n, int d) {
    // (n - 2)개의 1 출력
    for (int i = 0; i < n - 2; i++)
        cout << 1 << " ";
    // 하나의 2 출력
    cout << 2 << " ";
    // 마지막으로 (n + d) 출력
    cout << n + d << endl;
}

int main() {
    int N = 5, D = 8;
    getNNumbers(N, D);
}

실행 결과

1 1 1 2 13

결과 검증

출력된 값이 조건을 만족하는지 확인해 보겠습니다.

• 합: 1 + 1 + 1 + 2 + 13 = 18
• 곱: 1 × 1 × 1 × 2 × 13 = 26
• 차이: 26 − 18 = 8 (입력값 D = 8과 일치)

이처럼 시간 복잡도 O(N)으로 문제를 즉시 해결할 수 있으며, 추가적인 탐색이나 반복 계산이 전혀 필요하지 않습니다.