n명의 사람이 있을 때, 각 사람은 혼자 있거나 다른 사람과 한 쌍(pair)을 이룰 수 있습니다. 이때 이 사람들을 배치할 수 있는 총 방법의 수를 구하는 것이 이번 문제의 목표입니다.
문제 예시
입력 : 3
출력 : 4
설명 : [{1}, {2}, {3}], [{1, 2}, {3}], [{1}, {2, 3}], [{1, 3}, {2}]
위 네 가지가 3명의 사람을 배치할 수 있는 유일한 방법입니다.
입력 : 6
출력 : 76
3명의 경우 각 사람이 모두 단독으로 있는 경우 하나와, 두 명씩 짝을 이루고 나머지 한 명이 단독으로 있는 세 가지 경우, 총 네 가지 방법이 존재합니다.
해결 접근 방법
이 문제는 영 타블로(Young Tableau) 점화식을 활용하면 효율적으로 해결할 수 있습니다. n명의 사람을 배치하는 방법의 수를 A[n]이라 할 때, 다음 점화식이 성립합니다.
A[n] = A[n-1] + (n-1) * A[n-2]
점화식의 직관적 의미
- A[n-1]: n번째 사람이 누구와도 짝을 맺지 않고 혼자 있는 경우의 수
- (n-1) * A[n-2]: n번째 사람이 나머지 (n-1)명 중 한 명과 짝을 이루는 경우. 짝 상대는 (n-1)가지이며, 남은 (n-2)명을 배치하는 방법은 A[n-2]가지입니다.
두 경우를 더하면 전체 경우의 수가 됩니다. 시간 복잡도는 O(n), 공간 복잡도 역시 배열을 사용하므로 O(n)입니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
int Young_Tableau(int n){
int A[n + 1]; // 정답을 저장할 배열
A[1] = 1; // 초기값
A[2] = 2; // 초기값
// 영 타블로 점화식을 이용해 정답 계산
for (int i = 3; i <= n; i++) {
A[i] = A[i - 1] + (i - 1) * A[i - 2];
}
return A[n]; // 정답 반환
}
int main(){
int n = 6;
cout << Young_Tableau(n);
return 0;
}
실행 결과
76
코드 설명
위 코드는 영 타블로 점화식을 그대로 구현한 것입니다. 먼저 초기값으로 A[1] = 1, A[2] = 2를 설정한 뒤, 3부터 n까지 반복하면서 바로 앞의 두 값(A[i-1], A[i-2])을 배열 인덱스로 참조해 점화식에 대입합니다. 이렇게 하면 매번 재귀 호출로 같은 값을 다시 계산하지 않아도 되므로, 동적 계획법(DP) 방식으로 선형 시간 안에 답을 구할 수 있습니다.
마무리
이번 글에서는 n명의 사람을 혼자 또는 두 명씩 짝짓는 모든 경우의 수를 구하는 문제를 다루었습니다. 영 타블로 점화식을 활용한 C++ 풀이를 살펴보았으며, 동일한 로직은 C, Java, Python 등 다른 언어로도 손쉽게 작성할 수 있습니다. 큰 입력값을 다룰 때는 오버플로우를 방지하기 위해 long long 자료형이나 모듈러 연산을 적용하는 것도 고려해 보세요. 이 튜토리얼이 여러분에게 도움이 되기를 바랍니다.