[C++] 백준 1947번 선물 전달

n명의 사람이 선물을 한개씩 준비해서 자신이 아닌 사람에게 나누어줄 때

n명의 사람들은 선물을 하나씩 받게 됩니다. (2개 이상 받거나, 안 받을 수 없음)

이 때 줄 수 있는 경우의 수를 구하는 문제입니다.

 

다이나믹 프로그래밍, 완전 순열 문제입니다.

※ 완전 순열 : n명의 사람이 각각 자신의 모자를 벗어두었다가,

                  다시 쓰는데 모든 사람이 자기 것이 아닌 모자를 쓰는 방법의 수

 

1. 1:1로 선물을 교환한 경우

2. 다른 사람에게 하나를 주었을 경우

두 가지가 있습니다.

 

1번의 경우 1:1로 교환했을 때 다른 남은 사람들은 n-2명입니다.

               이는 memo[n-2]의 값을 나타냅니다.

2번의 경우 (1번->2번)에게 선물을 주었을 때 남은 사람들은 n-1명 입니다.

               이는 memo[n-1]의 값을 나타냅니다.

위와 같은 방법을 자신을 제외한 n-1번 반복할 수 있습니다.

이를 나타내면 

memo[n] = (n-1)(memo[n-2] + memo[n-1]);

로 나타낼 수 있습니다.

 

#include <iostream>
using namespace std; 

long long int memo[1000001] = {0, };  // 큰 값을 저장하기 위한 타입형

int main(int argc, char *argv[]) 
{ 
    int num; 

    memo[0] = 0; 
    memo[1] = 0; 
    memo[2] = 1; 
    memo[3] = 2; 
    cin >> num; 
    for (int i = 4; i <= num; ++i) { 
        memo[i] = ((i - 1) * (memo[i - 1] + memo[i - 2])% 1000000000); 
    } 
    cout << memo[num]; 

    return 0; 
}