C++로 해결하는 친구 페어링(Friends Pairing) 문제 완벽 가이드

이 문제에서는 그룹에 속한 친구의 수를 나타내는 양의 정수 N이 주어지며, 친구 페어링 문제(Friends Pairing Problem)를 해결하는 프로그램을 작성하는 것이 목표입니다.

그룹의 각 친구는 혼자 남아 있거나, 다른 친구 한 명과 짝을 이룰 수 있습니다. 단, 각 친구는 최대 한 번만 페어링에 참여할 수 있습니다.

문제 이해를 위한 예시

입력: n = 3
출력: 4
설명:
그룹의 3명을 A, B, C라고 합시다.
페어링은 다음과 같이 구성할 수 있습니다:
{A}, {B}, {C}
{A, B}, {C}
{A, C}, {B}
{A}, {B, C}

해결 접근 방식

이 문제를 해결하는 한 가지 방법은 n명의 친구에 대해 가능한 모든 페어링 조합의 개수를 구하는 일반 공식을 찾는 것입니다.

그룹에 n명의 친구가 있고, 이들이 짝을 이루는 방법의 수를 f(n)이라고 하겠습니다.

각 친구는 혼자 남거나 그룹 내 다른 친구와 짝을 이룰 수 있습니다. 두 경우를 살펴보겠습니다.

경우 1 − N번째 친구가 혼자 남기로 선택하면, 그룹 멤버가 한 명 줄어들고 다음 재귀 호출은 (N-1), 즉 f(N-1)부터 시작됩니다.
경우 2 − N번째 친구가 다른 멤버와 짝을 이루기로 선택하면, 나머지 (N-2)명이 남게 되며 다음 재귀 호출은 N-2부터 시작됩니다. 따라서 재귀 관계식은 f(N) = f(N-1) + (N-1) * f(N-2)가 됩니다.

N번째 친구가 자신과 짝을 이룰 상대는 (N-1)명 중에서 선택할 수 있으므로, 경우 2에는 (N-1)을 곱해주는 것이 핵심입니다.

이제 이 점화식을 활용한 여러 가지 구현 방법을 살펴보겠습니다.

방법 1: 동적 계획법(DP 배열) 활용

아래 프로그램은 DP 배열을 사용하여 솔루션의 동작을 보여줍니다.

#include <iostream>
using namespace std;

int countGroupPairing(int N){
    int dpArr[N + 1];
    for (int i = 0; i <= N; i++) {
        if (i <= 2)
            dpArr[i] = i;
        else
            dpArr[i] = dpArr[i - 1] + (i - 1) * dpArr[i - 2];
    }
    return dpArr[N];
}
int main(){
    int N = 6;
    cout<<"그룹에 속한 친구의 수는 "<<N<<endl;
    cout<<"가능한 총 페어링 수는 "<<countGroupPairing(N);
    return 0;
}

출력 결과

그룹에 속한 친구의 수는 6
가능한 총 페어링 수는 76

이 방법은 시간 복잡도 O(N), 공간 복잡도 O(N)으로 모든 중간 결과를 배열에 저장합니다.

방법 2: 메모이제이션을 활용한 재귀 접근

재귀적으로 문제를 해결하되, 이미 계산된 값을 메모이제이션하여 저장함으로써 중복 연산을 제거할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
int dpArr[1000];

int countGroupPairing(int N){
    memset(dpArr, -1, sizeof(dpArr));
    if (dpArr[N] != -1)
        return dpArr[N];
    if (N > 2)
        return dpArr[N] = countGroupPairing(N - 1) + (N - 1) * countGroupPairing(N - 2);
    else
        return dpArr[N] = N;
}
int main(){
    int N = 6;
    cout<<"그룹에 속한 친구의 수는 "<<N<<endl;
    cout<<"가능한 총 페어링 수는 "<<countGroupPairing(N);
    return 0;
}

출력 결과

그룹에 속한 친구의 수는 6
가능한 총 페어링 수는 76

방법 3: 피보나치 수열 최적화 기법 적용

문제를 해결하는 또 다른 방법은 피보나치 수열 계산 방식을 최적화하여 이 솔루션에 맞게 변형하는 것입니다. 이전 두 값만 유지하면 되므로 공간 복잡도를 O(1)까지 줄일 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
int dpArr[1000];

int countGroupPairing(int N){
    int val1 = 1, val2 = 2, val3 = 0;
    if (N <= 2) {
        return N;
    }
    for (int i = 3; i <= N; i++) {
        val3 = val2 + (i - 1) * val1;
        val1 = val2;
        val2 = val3;
    }
    return val3;
}
int main(){
    int N = 6;
    cout<<"그룹에 속한 친구의 수는 "<<N<<endl;
    cout<<"가능한 총 페어링 수는 "<<countGroupPairing(N);
    return 0;
}

출력 결과

그룹에 속한 친구의 수는 6
가능한 총 페어링 수는 76

마무리

친구 페어링 문제는 점화식 f(n) = f(n-1) + (n-1) × f(n-2)를 세울 수 있다면 다양한 방식으로 해결할 수 있는 대표적인 동적 계획법 문제입니다. 입력 크기가 작다면 단순 재귀로도 충분하지만, 효율성이 중요한 환경에서는 반복문과 두 변수만 사용하는 최적화 방법(방법 3)이 시간 복잡도 O(N), 공간 복잡도 O(1)으로 가장 우수한 선택입니다.