[1947번] 선물 전달

문제 출처 :

https://www.acmicpc.net/problem/1947

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

3. 완전순열

dp[i] :: i명의 사람이 선물을 나눌 수 있는 방법의 수

dp[1] = 0이고

dp[2] = 1임이 자명하다.

이제 dp[i] (i >= 3)에 대해 생각해보자.

이때 1번 사람은 항상 i번 사람의 선물을 가진다 가정하자.

이렇게 된다면 i번 사람은 2가지 경우를 가질 수 있게 된다.

1. n이 1번 선물을 선택할 경우

1번과 n번이 서로 교환한 상태이니 dp[n-2]가지 경우를 가질 수 있다.

2. n이 1번 선물을 선택하지 않을 경우

이때는 1번이 n번에게만 선물을 준 상태이니 결국 dp[n-1]가지 경우를 가질 수 있다.

이때 1,2번 모든 경우에서 1번 사람이 n번만을 선택할 경우만 생각했으나 1번은 n-1번 사람의 모자를 아무거나 선택해도 된다.

따라서 점화식 dp[n] = (n-1)(dp[n-1] + dp[n-2])가 성립된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
 
using namespace std;
 
const long long MOD = 1000000000;
 
long long dp[1000002];
 
int main()
{
    dp[1] = 0;
    dp[2] = 1;
 
    int n;
    cin >> n;
 
    for (int i = 3; i <= n; i++)
        dp[i] = (i - 1)*(dp[i - 2] + dp[i - 1]) % MOD;
    
    cout << dp[n];
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>