[BOJ 1947] 선물 전달

- 문제 요약

 

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

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

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

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

 

 

- 알고리즘 정리

 

직접 가능한 수를 만들어보며 점화식을 구해줬습니다.

 

n = 0 (0)

n = 1 (0)

n = 2 (1)

n = 3 (2)

n = 4 (9)

n = 5 (44)

 

이런 식으로 경우의 수를 구하며 가능한 경우를 직접 그리다 보면, 아래와 같은 점화식이 나옵니다.

dp[i] = (dp[i-1] + dp[i-2]) * (i-1)

 

나온 값을 1,000,000,000으로 나눠서 테이블에 저장해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1000005
#define MOD 1000000000
typedef long long ll;
int n;
ll dp[MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	dp[1]=0;
	dp[2]=1;
	dp[3]=2;
	for(int i=4;i<=n;i++){
		dp[i]=((dp[i-1]+dp[i-2])*(i-1))%MOD;
	}
	cout<<dp[n];
}

코드 제출 결과