C++로 방정식을 만족하는 6개 변수 조합(sextuplet) 개수 구하기

문제 정의

이 글에서는 주어진 방정식을 만족하는 여섯 개 변수 조합(sextuplet)의 개수를 구하는 방법을 살펴봅니다. 예시로 아래와 같은 방정식을 사용하며, 이 식을 만족하는 a, b, c, d, e, f 값의 조합을 모두 찾아야 합니다.

( a + b + c ) * e / d = f

식을 재배열하면 다음과 같이 표현할 수 있습니다.

( a + b + c ) = ( f * d ) / e

주어진 문제에 대한 간단한 예시는 다음과 같습니다.

입력 : arr [ ] = { 1, 3 }
출력 : 4
설명 : ( a, b, c, e, f ) = 1, d = 3
   ( a, b, c, d, e ) = 1, f = 3
   ( a, b, c ) = 1, ( d, e, f ) = 3
   ( a, b, c, d, f ) = 3, ( e ) = 1

입력 : arr [ ] = { 2, 5 }
출력 : 3

해결 접근 방법

이 문제는 단순 무식(brute-force) 방식으로 해결할 수 있습니다.

단순 탐색(Naive) 접근법

좌변(LHS)과 우변(RHS)을 기준으로 생각해 보면, 먼저 좌변에서 나올 수 있는 모든 결과값을 계산하여 하나의 배열에 저장합니다. 마찬가지로 우변의 모든 가능한 결과값을 담은 배열도 생성합니다.

그런 다음 두 배열을 비교하여 같은 값이 발견될 때마다 카운트를 증가시키고, 최종적으로 그 결과를 출력하면 됩니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
int findsamenumbers(int *arr1, int *arr2, int n){
    int i = 0, j = 0, k = 0, count=0;
    while(( i < n*n*n+1) && (j < n*n*n+1)){
        if(arr1[i] < arr2[j])
            i++;
        else if(arr1[i] == arr2[j]){
            count++;
        int temp = arr1[i];
        while(temp==arr1[++i]){
            count++;
        }
        while(temp==arr2[++j]){
            count++;
        }
    }
    else
        j++;
    }  
    return count;
}
int main(){
    int arr[] = {2,5};
    int n = sizeof(arr)/sizeof(arr[0]);
    // 좌변 배열의 모든 가능한 값 생성
    int index = 0,i;
    int LHS[n*n*n ];
    for ( i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                LHS[index++] = (arr[i] * arr[j]) / arr[k];
            }
        }
    }
    // 우변 배열의 모든 가능한 값 생성
    int RHS[n*n*n ];
    index=0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = 0; k < n; k++){
                RHS[index++] = (arr[i] + arr[j] + arr[k]);
            }
        }
    }
    sort(RHS, RHS + (n*n*n));
    sort(LHS, LHS + (n*n*n));
    int result = findsamenumbers(LHS, RHS, n);
    cout<<"Number of sextuplets that satisfy an equation: "<<result;
    return 0;
}

실행 결과

Number of sextuplets that satisfy an equation: 3

프로그램 설명

이 프로그램에서는 좌변과 우변의 모든 결과값을 저장하기 위해 두 개의 배열을 생성합니다. 세 겹의 중첩 반복문을 사용하여 (a, b, c)의 모든 가능한 값은 좌변(LHS) 배열에, (d, e, f)의 모든 가능한 값은 우변(RHS) 배열에 차례대로 저장합니다. 이후 두 배열을 각각 정렬한 뒤, 같은 값을 찾기 위해 findsamenumbers() 함수에 전달합니다.

findsamenumbers() 함수 내부에서는 두 포인터를 활용해 정렬된 배열을 순회하며 동일한 값을 확인합니다. 같은 값을 가진 두 원소를 발견하면, 해당 숫자가 각 배열에서 몇 번 등장하는지 빈도까지 계산하여 모든 가능한 조합을 빠짐없이 카운트합니다.

if(arr1[i] == arr2[j]){
   count++;
   int temp = arr1[i];
   while(temp==arr1[++i]){
      count++;
   }
   while(temp==arr2[++j]){
      count++;
   }

결론

이 글에서는 주어진 배열에서 방정식 (a + b + c) * e / d = f를 만족하는 여섯 개 변수 조합(sextuplet)의 개수를 구하는 문제를 해결했습니다. 6개 변수로 이루어진 방정식의 모든 가능한 변수 값을 탐색했으며, 이 접근법은 C, Java, Python 등 다른 프로그래밍 언어로도 동일하게 구현할 수 있습니다.