어떤 그룹에 n명의 친구가 있다고 가정해 봅시다. 각 사람은 혼자 남을 수도 있고, 다른 친구와 한 쌍(pair)을 이룰 수도 있습니다. 이때 친구들이 혼자 있거나 짝을 이루는 모든 가능한 방법의 수를 구하는 것이 이 문제의 목표입니다.
여기서 한 가지 중요한 조건이 있습니다. 두 친구 p와 q가 한 쌍을 이룰 때, (p, q)와 (q, p)는 같은 경우로 봅니다. 즉, 순서는 고려하지 않습니다.
문제 접근 방식
n명의 친구가 있을 때, 짝을 이루거나 혼자 남는 방법의 수를 f(n)이라고 정의하겠습니다. 그러면 n번째 사람의 입장에서 두 가지 선택지가 있습니다.
- n번째 사람이 혼자 남는 경우: 나머지 (n-1)명에 대해 같은 문제를 다시 풀면 됩니다. 즉, f(n-1)가지입니다.
- n번째 사람이 누군가와 짝을 이루는 경우: 나머지 (n-1)명 중 한 명과 짝이 될 수 있으므로 (n-1)가지의 선택이 가능하고, 각 선택마다 남은 (n-2)명에 대해 f(n-2)가지의 경우가 생깁니다. 따라서 (n-1) × f(n-2)가지입니다.
이를 점화식으로 정리하면 다음과 같습니다.
f(n) = f(n-1) + (n-1) × f(n-2)
입력과 출력
입력: 친구의 수. 예를 들어 5. 출력: 짝을 지을 수 있는 모든 방법의 수. 여기서 답은 26입니다.
알고리즘
countPairs(n)
입력: 친구의 수 n
출력: n명의 친구를 짝짓는 방법의 수
Begin
크기가 n + 1인 배열 pairs 선언
pairs[0] := 0, pairs[1] := 1, pairs[2] := 2
for i from 3 to n, do
pairs[i] := pairs[i-1] + (i-1) * pairs[i-2]
done
return pairs[n]
End배열을 사용하면 이미 계산한 값을 다시 구하지 않아도 되므로, 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int countPairs(int n) {
int pairs[n + 1]; // i번째까지의 짝짓기 경우의 수
// 0~2명일 때는 각각 0~2가지 조합이 존재
pairs[0] = 0;
pairs[1] = 1;
pairs[2] = 2;
// 3부터 n까지 배열을 채워나감
for (int i = 3; i <= n; i++)
pairs[i] = pairs[i-1] + (i-1) * pairs[i-2];
return pairs[n];
}
int main() {
int n;
cout << "Enter numbers: "; cin >> n;
cout << "Number of ways to pair " << n << " friends: " << countPairs(n);
}실행 결과
Enter numbers: 5 Number of ways to pair 5 friends: 26
동작 원리 검증
친구가 5명일 때 결과가 26이 나오는 과정을 살펴보겠습니다.
- pairs[0] = 0 (사람이 없음)
- pairs[1] = 1 (혼자만 있는 경우)
- pairs[2] = 2 (둘 다 혼자이거나, 서로 짝을 이룸)
- pairs[3] = pairs[2] + 2 × pairs[1] = 2 + 2 = 4
- pairs[4] = pairs[3] + 3 × pairs[2] = 4 + 6 = 10
- pairs[5] = pairs[4] + 4 × pairs[3] = 10 + 16 = 26
이처럼 점화식을 활용하면 재귀 호출 없이도 선형 시간 안에 정답을 구할 수 있습니다. 참고로 이 수열은 전화번호 문제(Telephone Numbers) 또는 자움 수열(Involution Numbers)로 알려져 있으며, n명을 단독 또는 2인 그룹으로 나누는 방법의 수를 의미합니다.