문제 소개
코딩 대회에 N명의 참가자가 있다고 가정해 보겠습니다. 우리의 목표는 각 사람이 최대 한 명과만 짝을 이룰 수 있을 때, 가능한 짝 조합의 수를 구하는 것입니다. 하나의 짝은 최대 2명으로 구성되며, 참가자가 누구와도 짝을 맺지 않고 혼자 참여하는 경우도 허용됩니다.
이 문제는 다음과 같은 점화식(재귀 관계)을 통해 해결할 수 있습니다.
- n = 0 또는 n = 1일 때: count = 1 (남은 사람이 없거나 한 명뿐이므로 혼자 남는 방법 하나뿐)
- 어떤 사람이 혼자 남기로 선택한 경우: 문제의 크기가 n-1로 줄어듭니다.
- 어떤 사람이 다른 사람과 짝을 이룬 경우: 짝을 맺을 상대는 (n-1)가지이고, 나머지 인원은 n-2명이 되므로 (n-1) × makePairs(n-2)가 됩니다.
따라서 전체 점화식은 다음과 같습니다.
count = makePairs(p-1) + (p-1) * makePairs(p-2)
예제로 이해하기
입력 — persons = 3
출력 — 짝을 만드는 방법의 수: 4
설명
세 참가자가 a, b, c일 때 가능한 조합은 다음과 같습니다. (a,b), (c) → c가 혼자 남음 (a,c), (b) → b가 혼자 남음 (b,c), (a) → a가 혼자 남음 (a), (b), (c) → 모두 혼자 남음 총 방법의 수 = 4
입력 — persons = 2
출력 — 짝을 만드는 방법의 수: 2
설명
참가자가 a, b 두 명일 때 가능한 조합은 다음과 같습니다. (a,b) → 두 사람이 짝을 이룸 (a), (b) → 두 사람 모두 혼자 남음 총 방법의 수 = 2
프로그램의 접근 방식
- 참가자 수를 저장할 정수형 변수
person을 선언합니다. - 함수
makePairs(int p)는 참가자 수를 입력받아 짝을 지을 수 있는 모든 방법의 수를 반환합니다. - 초기 count 값은 0으로 설정합니다.
- p가 0 또는 1이면 유일한 선택지는 혼자 남는 것이므로 count를 1로 설정합니다. (기저 조건)
- 그 외의 경우, 한 사람이 혼자 남는 경우(makePairs(p-1))와 다른 사람과 짝을 맺는 경우((p-1) * makePairs(p-2))를 더하여 count를 계산합니다.
- 최종적으로 계산된 count 값이 짝을 만드는 방법의 총 개수로 반환됩니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int makePairs(int p){
int count=0;
// 기저 조건
if (p==0 || p==1)
{ count=1; }
else
{ count=makePairs(p-1) + (p-1)*makePairs(p-2); }
return count;
}
int main(){
int persons = 5;
cout <<"Number of ways to make pair ( or remain single ):"<<makePairs(persons);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Number of ways to make pair ( or remain single ): 26
추가 참고 사항
위 재귀 구현은 동일한 하위 문제를 반복해서 계산하므로 참가자 수가 커지면 시간 복잡도가 지수적으로 증가할 수 있습니다. 따라서 입력 크기가 클 때는 메모이제이션(memoization)이나 동적 계획법(DP)을 적용해 각 하위 문제를 한 번씩만 계산하도록 최적화하는 것이 좋습니다. 참고로 이 수열은 '전화번호 수열(Telephone Numbers)' 또는 'involutions'로 알려져 있으며, n명을 짝과 단독 참여 그룹으로 나누는 방법의 수를 나타냅니다.