이 문제에서 그룹의 친구 수를 나타내는 양의 정수 N이 제공됩니다. 우리의 임무는 FriendsPairing 문제를 해결하는 프로그램을 만드는 것입니다.
그룹의 각 친구는 독신으로 남거나 다른 친구와 짝을 이룰 수 있습니다. 그룹의 각 친구의 페어링은 한 번만 수행할 수 있습니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input: n = 3
Output: 4
Explanation:
Let’s say the 3 members of the group are A, B and C.
The pairing can be done as :
{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)
로 재귀적으로 호출됩니다.
이 문제를 해결할 수 있는 여러 가지 방법이 있습니다.
예시
솔루션 작동을 설명하는 프로그램
#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<<"The number of friends in the group is "<<N<<endl;
cout<<"The total number of possible pairs is "<<countGroupPairing(N);
return 0;
} 출력
The number of friends in the group is 6 The total number of possible pairs is 76
솔루션 구현을 위한 재귀적 접근 방식
예시
솔루션 작동을 설명하는 프로그램
#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<<"The number of friends in the group is "<<N<<endl;
cout<<"The total number of possible pairs is "<<countGroupPairing(N);
return 0;
} 출력
The number of friends in the group is 6 The total number of possible pairs is 76
문제를 해결하는 또 다른 방법은 주어진 솔루션에 맞도록 피보나치 급수를 최적화하는 것입니다.
예시
솔루션 작동을 설명하는 프로그램
#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<<"The number of friends in the group is "<<N<<endl;
cout<<"The total number of possible pairs is "<<countGroupPairing(N);
return 0;
} 출력
The number of friends in the group is 6 The total number of possible pairs is 76