친구 페어링 문제
n 명의 친구가 주어지면 각 사람은 독신으로 남을 수도 있고 다른 친구와 짝을 이룰 수도 있습니다. 각 친구는 한 번만 페어링할 수 있습니다. 친구가 독신으로 남거나 짝을 이룰 수 있는 방법의 총 수를 알아보세요.
예:
Input : n = 3 Output : 4 Explanation: {1} {2} {3} : all single {1} {2 3} : 2 and 3 paired but 1 is single. {1 2} {3} : 1 and 2 are paired but 3 is single. {1 3} {2} : 1 and 3 are paired but 2 is single. Note that {1 2} and {2 1} are considered same. Mathematical Explanation: The problem is simplified version of how many ways we can divide n elements into multiple groups. (here group size will be max of 2 elements). In case of n = 3 we have only 2 ways to make a group: 1) all elements are individual(111) 2) a pair and individual (21) In case of n = 4 we have 3 ways to form a group: 1) all elements are individual (1111) 2) 2 individuals and one pair (211) 3) 2 separate pairs (22) tinytextbf{수학 공식:} newline{frac{n!}{((g_1!)^xtimes (g_2!)^ytimes ... (g_n!)^z)times(x!times y!times...z!)}}spacespacetinytext{ ----- (1)} newline{tinytext{동일한 그룹 크기가 xy...z 번 반복되는 경우 답을 추가로 나누어야 합니다. x!y!...z!}} newline{tinytext{이제 사례 n=3, 그룹 크기 최대 크기 2, 최소 크기 1을 고려해 보겠습니다.}} newline{frac{3!}{(1!)^3times(3!)} space+space frac{3!}{(2!)^1times(1!)^1times(1!)^2}space = 4} newline{text{이제 사례 n=4를 고려해 보겠습니다.}} newline{frac{4!}{(1!)^4times(4!)} space+ frac{4!}{(2!)^1times(1!)^2times(2!)}space + space frac{4!}{(2!)^2times(2!)}space = 10}
권장 실습 친구 페어링 문제 시도해 보세요!n번째 사람에게는 두 가지 선택이 있습니다. 1) n번째 사람은 독신으로 남아 있으며 f(n - 1)에 대해 반복됩니다.2) n번째 사람은 나머지 n - 1명과 쌍을 이룹니다. (n - 1) * f(n - 2) 따라서 f(n)을 다음과 같이 재귀적으로 쓸 수 있습니다. f(n) = f(n - 1) + (n - 1) * f(n - 2)
위의 재귀 공식은 중복되는 하위 문제 동적 프로그래밍을 사용하여 문제를 해결할 수 있습니다.
C++ // C++ program for solution of // friends pairing problem #include using namespace std ; // Returns count of ways n people // can remain single or paired up. int countFriendsPairings ( int n ) { int dp [ n + 1 ]; // Filling dp[] in bottom-up manner using // recursive formula explained above. for ( int i = 0 ; i <= n ; i ++ ) { if ( i <= 2 ) dp [ i ] = i ; else dp [ i ] = dp [ i - 1 ] + ( i - 1 ) * dp [ i - 2 ]; } return dp [ n ]; } // Driver code int main () { int n = 4 ; cout < < countFriendsPairings ( n ) < < endl ; return 0 ; }
Java // Java program for solution of // friends pairing problem import java.io.* ; class GFG { // Returns count of ways n people // can remain single or paired up. static int countFriendsPairings ( int n ) { int dp [] = new int [ n + 1 ] ; // Filling dp[] in bottom-up manner using // recursive formula explained above. for ( int i = 0 ; i <= n ; i ++ ) { if ( i <= 2 ) dp [ i ] = i ; else dp [ i ] = dp [ i - 1 ] + ( i - 1 ) * dp [ i - 2 ] ; } return dp [ n ] ; } // Driver code public static void main ( String [] args ) { int n = 4 ; System . out . println ( countFriendsPairings ( n )); } } // This code is contributed by vt_m
Python3 # Python program solution of # friends pairing problem # Returns count of ways # n people can remain # single or paired up. def countFriendsPairings ( n ): dp = [ 0 for i in range ( n + 1 )] # Filling dp[] in bottom-up manner using # recursive formula explained above. for i in range ( n + 1 ): if ( i <= 2 ): dp [ i ] = i else : dp [ i ] = dp [ i - 1 ] + ( i - 1 ) * dp [ i - 2 ] return dp [ n ] # Driver code n = 4 print ( countFriendsPairings ( n )) # This code is contributed # by Soumen Ghosh.
C# // C# program solution for // friends pairing problem using System ; class GFG { // Returns count of ways n people // can remain single or paired up. static int countFriendsPairings ( int n ) { int [] dp = new int [ n + 1 ]; // Filling dp[] in bottom-up manner using // recursive formula explained above. for ( int i = 0 ; i <= n ; i ++ ) { if ( i <= 2 ) dp [ i ] = i ; else dp [ i ] = dp [ i - 1 ] + ( i - 1 ) * dp [ i - 2 ]; } return dp [ n ]; } // Driver code public static void Main () { int n = 4 ; Console . Write ( countFriendsPairings ( n )); } } // This code is contributed by nitin mittal.
PHP // PHP program solution for // friends pairing problem // Returns count of ways n people // can remain single or paired up. function countFriendsPairings ( $n ) { $dp [ $n + 1 ] = 0 ; // Filling dp[] in bottom-up // manner using recursive formula // explained above. for ( $i = 0 ; $i <= $n ; $i ++ ) { if ( $i <= 2 ) $dp [ $i ] = $i ; else $dp [ $i ] = $dp [ $i - 1 ] + ( $i - 1 ) * $dp [ $i - 2 ]; } return $dp [ $n ]; } // Driver code $n = 4 ; echo countFriendsPairings ( $n ) ; // This code is contributed // by nitin mittal. ?>
JavaScript < script > // Javascript program for solution of // friends pairing problem // Returns count of ways n people // can remain single or paired up. function countFriendsPairings ( n ) { let dp = []; // Filling dp[] in bottom-up manner using // recursive formula explained above. for ( let i = 0 ; i <= n ; i ++ ) { if ( i <= 2 ) dp [ i ] = i ; else dp [ i ] = dp [ i - 1 ] + ( i - 1 ) * dp [ i - 2 ]; } return dp [ n ]; } // Driver Code let n = 4 ; document . write ( countFriendsPairings ( n )); < /script>
산출
10
시간 복잡도: 에)
보조 공간 : 에)
또 다른 접근법: (재귀 사용)
C++ // C++ program for solution of friends // pairing problem Using Recursion #include using namespace std ; int dp [ 1000 ]; // Returns count of ways n people // can remain single or paired up. int countFriendsPairings ( int n ) { if ( dp [ n ] != -1 ) return dp [ n ]; if ( n > 2 ) return dp [ n ] = countFriendsPairings ( n - 1 ) + ( n - 1 ) * countFriendsPairings ( n - 2 ); else return dp [ n ] = n ; } // Driver code int main () { memset ( dp -1 sizeof ( dp )); int n = 4 ; cout < < countFriendsPairings ( n ) < < endl ; // this code is contributed by Kushdeep Mittal }
Java // Java program for solution of friends // pairing problem Using Recursion import java.io.* ; class GFG { static int [] dp = new int [ 1000 ] ; // Returns count of ways n people // can remain single or paired up. static int countFriendsPairings ( int n ) { if ( dp [ n ] != - 1 ) return dp [ n ] ; if ( n > 2 ) return dp [ n ] = countFriendsPairings ( n - 1 ) + ( n - 1 ) * countFriendsPairings ( n - 2 ); else return dp [ n ] = n ; } // Driver code public static void main ( String [] args ) { for ( int i = 0 ; i < 1000 ; i ++ ) dp [ i ] = - 1 ; int n = 4 ; System . out . println ( countFriendsPairings ( n )); } } // This code is contributed by Ita_c.
Python3 # Python3 program for solution of friends # pairing problem Using Recursion dp = [ - 1 ] * 1000 # Returns count of ways n people # can remain single or paired up. def countFriendsPairings ( n ): global dp if ( dp [ n ] != - 1 ): return dp [ n ] if ( n > 2 ): dp [ n ] = ( countFriendsPairings ( n - 1 ) + ( n - 1 ) * countFriendsPairings ( n - 2 )) return dp [ n ] else : dp [ n ] = n return dp [ n ] # Driver Code n = 4 print ( countFriendsPairings ( n )) # This code contributed by PrinciRaj1992
C# // C# program for solution of friends // pairing problem Using Recursion using System ; class GFG { static int [] dp = new int [ 1000 ]; // Returns count of ways n people // can remain single or paired up. static int countFriendsPairings ( int n ) { if ( dp [ n ] != - 1 ) return dp [ n ]; if ( n > 2 ) return dp [ n ] = countFriendsPairings ( n - 1 ) + ( n - 1 ) * countFriendsPairings ( n - 2 ); else return dp [ n ] = n ; } // Driver code static void Main () { for ( int i = 0 ; i < 1000 ; i ++ ) dp [ i ] = - 1 ; int n = 4 ; Console . Write ( countFriendsPairings ( n )); } } // This code is contributed by DrRoot_
PHP // PHP program for solution of friends // pairing problem Using Recursion // Returns count of ways n people // can remain single or paired up. function countFriendsPairings ( $n ) { $dp = array_fill ( 0 1000 - 1 ); if ( $dp [ $n ] != - 1 ) return $dp [ $n ]; if ( $n > 2 ) { $dp [ $n ] = countFriendsPairings ( $n - 1 ) + ( $n - 1 ) * countFriendsPairings ( $n - 2 ); return $dp [ $n ]; } else { $dp [ $n ] = $n ; return $dp [ $n ]; } } // Driver Code $n = 4 ; echo countFriendsPairings ( $n ) // This code is contributed by Ryuga ?>
JavaScript < script > // Javascript program for solution of friends // pairing problem Using Recursion let dp = new Array ( 1000 ); // Returns count of ways n people // can remain single or paired up. function countFriendsPairings ( n ) { if ( dp [ n ] != - 1 ) return dp [ n ]; if ( n > 2 ) return dp [ n ] = countFriendsPairings ( n - 1 ) + ( n - 1 ) * countFriendsPairings ( n - 2 ); else return dp [ n ] = n ; } // Driver code for ( let i = 0 ; i < 1000 ; i ++ ) dp [ i ] = - 1 ; let n = 4 ; document . write ( countFriendsPairings ( n )); // This code is contributed by rag2127 < /script>
산출
10
시간 복잡도: 에)
보조 공간 : 에)
위의 수식은 다음과 유사하므로 피보나치 수 반복적인 솔루션으로 공간을 최적화할 수 있습니다.
C++ #include using namespace std ; // Returns count of ways n people // can remain single or paired up. int countFriendsPairings ( int n ) { int a = 1 b = 2 c = 0 ; if ( n <= 2 ) { return n ; } for ( int i = 3 ; i <= n ; i ++ ) { c = b + ( i - 1 ) * a ; a = b ; b = c ; } return c ; } // Driver code int main () { int n = 4 ; cout < < countFriendsPairings ( n ); return 0 ; } // This code is contributed by mits
Java import java.io.* ; class GFG { // Returns count of ways n people // can remain single or paired up. static int countFriendsPairings ( int n ) { int a = 1 b = 2 c = 0 ; if ( n <= 2 ) { return n ; } for ( int i = 3 ; i <= n ; i ++ ) { c = b + ( i - 1 ) * a ; a = b ; b = c ; } return c ; } // Driver code public static void main ( String [] args ) { int n = 4 ; System . out . println ( countFriendsPairings ( n )); } } // This code is contributed by Ravi Kasha.
Python3 # Returns count of ways n people # can remain single or paired up. def countFriendsPairings ( n ): a b c = 1 2 0 ; if ( n <= 2 ): return n ; for i in range ( 3 n + 1 ): c = b + ( i - 1 ) * a ; a = b ; b = c ; return c ; # Driver code n = 4 ; print ( countFriendsPairings ( n )); # This code contributed by Rajput-Ji
C# using System ; class GFG { // Returns count of ways n people // can remain single or paired up. static int countFriendsPairings ( int n ) { int a = 1 b = 2 c = 0 ; if ( n <= 2 ) { return n ; } for ( int i = 3 ; i <= n ; i ++ ) { c = b + ( i - 1 ) * a ; a = b ; b = c ; } return c ; } // Driver code public static void Main ( String [] args ) { int n = 4 ; Console . WriteLine ( countFriendsPairings ( n )); } } // This code has been contributed by 29AjayKumar
PHP // Returns count of ways n people // can remain single or paired up. function countFriendsPairings ( $n ) { $a = 1 ; $b = 2 ; $c = 0 ; if ( $n <= 2 ) { return $n ; } for ( $i = 3 ; $i <= $n ; $i ++ ) { $c = $b + ( $i - 1 ) * $a ; $a = $b ; $b = $c ; } return $c ; } // Driver code $n = 4 ; print ( countFriendsPairings ( $n )); // This code is contributed by mits ?>
JavaScript < script > // Returns count of ways n people // can remain single or paired up. function countFriendsPairings ( n ) { let a = 1 b = 2 c = 0 ; if ( n <= 2 ) { return n ; } for ( let i = 3 ; i <= n ; i ++ ) { c = b + ( i - 1 ) * a ; a = b ; b = c ; } return c ; } // Driver code let n = 4 ; document . write ( countFriendsPairings ( n )); // This code is contributed by avanitrachhadiya2155 < /script>
산출
10
시간 복잡도: 에)
보조 공간 : 오(1)
또 다른 접근법: 수학을 사용하여 위의 문제를 해결할 수 있으므로 아래의 솔루션은 동적 프로그래밍을 사용하지 않고 수행됩니다.
C++ // C++ soln using mathematical approach #include using namespace std ; void preComputeFact ( vector < long long int >& fact int n ) { for ( int i = 1 ; i <= n ; i ++ ) fact . push_back ( fact [ i - 1 ] * i ); } // Returns count of ways n people // can remain single or paired up. int countFriendsPairings ( vector < long long int > fact int n ) { int ones = n twos = 1 ans = 0 ; while ( ones >= 0 ) { // pow of 1 will always be one ans += fact [ n ] / ( twos * fact [ ones ] * fact [( n - ones ) / 2 ]); ones -= 2 ; twos *= 2 ; } return ans ; } // Driver code int main () { vector < long long int > fact ; fact . push_back ( 1 ); preComputeFact ( fact 100 ); int n = 4 ; cout < < countFriendsPairings ( fact n ) < < endl ; return 0 ; } // This code is contributed by rajsanghavi9.
Java // Java soln using mathematical approach import java.util.* ; class GFG { static Vector < Integer > fact ; static void preComputeFact ( int n ) { for ( int i = 1 ; i <= n ; i ++ ) fact . add ( fact . elementAt ( i - 1 ) * i ); } // Returns count of ways n people // can remain single or paired up. static int countFriendsPairings ( int n ) { int ones = n twos = 1 ans = 0 ; while ( ones >= 0 ) { // pow of 1 will always be one ans += fact . elementAt ( n ) / ( twos * fact . elementAt ( ones ) * fact . elementAt (( n - ones ) / 2 )); ones -= 2 ; twos *= 2 ; } return ans ; } // Driver code public static void main ( String [] args ) { fact = new Vector <> (); fact . add ( 1 ); preComputeFact ( 100 ); int n = 4 ; System . out . print ( countFriendsPairings ( n ) + 'n' ); } } // This code is contributed by umadevi9616
Python3 # Python3 soln using mathematical approach # factorial array is stored dynamically fact = [ 1 ] def preComputeFact ( n ): for i in range ( 1 n + 1 ): fact . append (( fact [ i - 1 ] * i )) # Returns count of ways n people # can remain single or paired up. def countFriendsPairings ( n ): ones = n twos = 1 ans = 0 while ( ones >= 0 ): # pow of 1 will always be one ans = ans + ( fact [ n ] // ( twos * fact [ ones ] * fact [( n - ones ) // 2 ])) ones = ones - 2 twos = twos * 2 return ( ans ) # Driver Code # pre-compute factorial preComputeFact ( 1000 ) n = 4 print ( countFriendsPairings ( n )) # solution contributed by adarsh_007
C# // C# program to implement the approach using System ; using System.Collections.Generic ; public class GFG { // initializing the fact list static List < int > fact = new List < int > (); // computing the next n values of fact static void preComputeFact ( int n ) { for ( int i = 1 ; i <= n ; i ++ ) { fact . Add ( fact [ i - 1 ] * i ); } } // Returns count of ways n people // can remain single or paired up. static int countFriendsPairings ( int n ) { int ones = n ; int twos = 1 ; int ans = 0 ; while ( ones >= 0 ) { // pow of 1 will always be one ans += fact [ n ] / ( twos * fact [ ones ] * fact [( n - ones ) / 2 ]); ones -= 2 ; twos *= 2 ; } return ans ; } // driver code static public void Main () { // initializing the first element of fact fact . Add ( 1 ); preComputeFact ( 100 ); int n = 4 ; Console . Write ( countFriendsPairings ( n )); } } // this code is contributed by phasing17
JavaScript < script > // Javascript soln using mathematical approach // factorial array is stored dynamically let fact = [ 1 ]; function preComputeFact ( n ) { for ( let i = 1 ; i < n + 1 ; i ++ ) { fact . push (( fact [ i - 1 ] * i )); } } // Returns count of ways n people // can remain single or paired up. function countFriendsPairings ( n ) { let ones = n let twos = 1 ; let ans = 0 ; while ( ones >= 0 ) { // pow of 1 will always be one ans = ans + Math . floor ( fact [ n ] / ( twos * fact [ ones ] * fact [( n - ones ) / 2 ])) ones = ones - 2 twos = twos * 2 } return ans ; } // Driver Code // pre-compute factorial preComputeFact ( 1000 ) n = 4 document . write ( countFriendsPairings ( n )) // This code is contributed by ab2127 < /script>
산출
10
시간 복잡도: 에)
보조 공간: 에)
