[BOJ/C++] 1947 선물 전달

문제에서 요구하는 수열이 완전순열이라고 합니다.

완전순열의 점화식을 아는 유무가 중요할 것 같습니다.

나를 제외한 모두가 선물을 하나씩 받는 경우의 수를 구해봅시다.

첫번째 경우

• 1, 2번이 서로에게 선물을 전달한 경우

1, 2번은 선물 교환이 끝났기 때문에 남은 3명이서 전달하는 경우의 수가 남습니다.

1번은 (N-1)명한테 선물을 줄 수 있으니 다음과 같은 점화식을 얻을 수 있습니다.

$(N-1)*DP[N-2]$

두번째 경우

• 각자 다른 사람에게 선물을 전달한 경우

1번은 N-1명한테 선물을 줄 수 있고 남은 4명이서 선물을 전달하는 경우의 수가 남습니다.

$(N-1)*DP[N-1]$

N명이 선물을 교환하는 점화식은 위 두가지 경우의 합인

$(N-1)*(DP[N-1] + DP[N-2])$

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static int64 DP[1000001] = {};

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);

   int N;
   cin >> N;

   DP[1] = 0;
   DP[2] = 1;

   for(int i=3; i<=N; i++)
   {
       DP[i] = (i-1) * (DP[i - 1] + DP[i - 2]) % 1000000000;
   }

   cout << DP[N];


   return 0;
}