[TopCoder] HandsShaking(악수)

원형 테이블에 둘러앉아 있는 n명의 사업가들의 모임을 생각해보자. 회의를 시작하려면, 그들은 악수를 해야 한다. 각각의 사업가들은 정확히 한 명의 다른 사업가와 악수를 한다. 모든 악수는 동시에 이루어집니다. 우리는 서로 팔짱을 끼지 않으면 악수가 완벽하다고 말한다. int n이 주어졌을 때, n명의 사업가들에게 존재하는 완벽한 쉐이크의 수를 반환한다. 자세한 설명은 예를 참조하십시오.

Definition

Class:

 

HandsShaking

Method:

 

countPerfect

Parameters:

 

int

Returns:

 

long long

Method signature:

 

long long countPerfect(int n)

(be sure your method is public)

 

Examples

0)

2

Returns: 1

Two businessmen have only one possibility - just to shake each other's hand.

 

1)

4

Returns: 2

Two out of three possible shakes are perfect.

  

  

2)

8

Returns: 14

 

---

카탈란 수를 이용하여 푸는 문제이다. 

 

using namespace std;

class HandsShaking{
    public:
    long long countPerfect(int n){
        long long *dp = new long long[n/2 + 1];
        dp[0] = 1;
        
        for(int i=1; i<=n/2; i++){
            dp[i] = 0;
            for(int j=0; j<i; j++){
                dp[i] += dp[j]*dp[i-j-1];
            }
        }
        return dp[n/2];
    }
};

전체 코드이다.

 

        long long *dp = new long long[n/2 + 1];
        dp[0] = 1;

전체 사람 수가 n명이라면 악수가 이루어지는 쌍은 총 n/2쌍이므로 그만큼의 배열을 선언한다. 

 

        for(int i=1; i<=n/2; i++){
            dp[i] = 0;
            for(int j=0; j<i; j++){
                dp[i] += dp[j]*dp[i-j-1];
            }
        }

카탈란 수를 전개한다. 

 

        return dp[n/2];