C++로 하나의 변수가 빠진 n개의 합 방정식에서 n개 변수 값 구하기

이 문제에서는 n개의 변수가 있고, 각 항이 자기 자신을 제외한 나머지 (n−1)개 변수의 합으로 구성된 배열 sum[]이 주어집니다.

Sum[1] = x2 + x3 + x4 + … + xn
Sum[2] = x1 + x3 + x4 + … + xn
.
.
Sum[i] = x1 + … + x(i−1) + x(i+1) + … + xn
.
.
Sum[n] = x1 + x2 + x3 + … + x(n−1)

우리가 해야 할 일은 이 합 배열만 가지고 x1, x2, …, xn의 실제 값을 역으로 계산하는 것입니다.

예시로 문제 이해하기

입력

sum[] = {6, 6, 6, 6, 6, 6, 6}

출력

x1 = 1, x2 = 1, x3 = 1, x4 = 1, x5 = 1, x6 = 1, x7 = 1

설명

arr[1] = 1 + 1 + 1 + 1 + 1 + 1 = 6

풀이 접근법

먼저 모든 변수의 총합을 sumX라고 정의해 봅시다.

sumX = x1 + x2 + x3 + … + xn

그러면 합 배열의 각 값은 다음과 같이 변형하여 표현할 수 있습니다.

sum[1] = x2 + x3 + x4 + … + xn
       = −x1 + x1 + x2 + x3 + x4 + … + xn
       = sumX − x1

같은 방식으로 나머지 항들도 일반화할 수 있습니다.

sum[2] = sumX − x2
sum[3] = sumX − x3
.
sum[i] = sumX − xi
.
sum[n] = sumX − xn

이제 합 배열의 모든 값을 더해 보면,

sum[1] + sum[2] + … + sum[n] = (sumX − x1) + (sumX − x2) + … + (sumX − xn)
arrSum = n × sumX − (x1 + x2 + x3 + … + xn)
arrSum = n × sumX − sumX
arrSum = sumX × (n − 1)

따라서 전체 변수의 합 sumX는 아주 간단하게 구할 수 있습니다.

sumX = arrSum / (n − 1)

sumX를 알아냈다면, 각 변수의 값은 다음 식으로 즉시 계산됩니다.

x1 = sumX − sum[1]
x2 = sumX − sum[2]
..
xi = sumX − sum[i]
..
xn = sumX − sum[n]

동작 원리를 보여주는 C++ 프로그램

예제 코드

#include <iostream>
using namespace std;

void calcSumVariables(int sum[], int n) {
    float SUMX = 0;
    for (int i = 0; i < n; i++) {
        SUMX += sum[i];
    }
    SUMX /= (n - 1);
    for (int i = 0; i < n; i++)
        cout << "\nx" << (i + 1) << " = " << (SUMX - sum[i]);
}

int main(){
    int sum[] = {3, 8, 6, 7, 4, 5, 9 };
    int N = sizeof(sum) / sizeof(sum[0]);
    cout << "The value of variables that form the sum are ";
    calcSumVariables(sum, N);
    return 0;
}

출력 결과

합을 이루는 변수들의 값은 다음과 같습니다.

x1 = 4
x2 = -1
x3 = 1
x4 = 0
x5 = 3
x6 = 2
x7 = -2

복잡도 분석

이 알고리즘은 배열을 두 번 순회하므로 시간 복잡도는 O(n)입니다. 또한 상수 개수의 변수만 사용하기 때문에 공간 복잡도는 O(1)로, 매우 효율적인 선형 시간 풀이입니다.