[Gold / 1947] 선물 전달

문제 링크

---

🔷 분류

수학, 다이나믹 프로그래밍, 조합론

✒️ 문제 설명

이번 ACM-ICPC 대회에 참가한 모든 사람들은 선물을 하나씩 준비했다.

대회가 끝나고 난 후에 각자 선물을 전달하려고 할 때, 선물을 나누는 경우의 수를 구하는 프로그램을 작성하시오.

모든 사람은 선물을 하나씩 받으며, 자기의 선물을 자기가 받는 경우는 없다.

⬅️ 입력

첫째 줄에 ACM-ICPC 대회에 참가한 학생의 수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

➡️ 출력

경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다.

💻 코드 (C++)

#include <iostream>
#define MOD 1000000000
using namespace std;

long D[1000001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	D[1] = 0;
	D[2] = 1;
	
	for(int i = 3; i <= n; i++) {
		D[i] = (i - 1) * (D[i - 2] + D[i - 1]) % MOD;
	}
	
	cout << D[n];
	
	return 0;
}