선물 전달( BOJ 1947 )

1947. 선물 전달 : https://www.acmicpc.net/problem/1947

1947번: 선물 전달

 

1. 문제 파악하기

N명의 사람이 선물을 교환해야 합니다. 단, 다른 사람에게 꼭 자신의 선물을 건네야 합니다.

또한, N의 값이 1,000,000까지 커질 수 있으므로 long long int형을 사용해야 한다는 사실을 유념해야 합니다.

 

2. 문제 해결하기

DP[N]을 N명의 사람이 선물을 교환하는 방법이라고 정의하겠습니다.

 

만약 1번 사람이 K번 사람과 선물을 교환했다고 가정해봅시다. 그렇다면 위 상황은 (N-2)명의 사람들만 서로 선물을 교환해야 하는 상황으로 바뀌며, 이 때 방법의 수는 DP[N-2]가 됩니다. 그리고, 1번 사람이 선물을 교환할 K를 고르는 방법의 수는 (N-1)개이기 때문에 나올 수 있는 총 경우의 수는  (N-1)*DP[N-2] 가 됩니다.

 

만약 1번 사람이 K번 사람의 선물을 받고, K번 사람은 1번 사람이 아닌 다른 사람의 선물을 받았다고 가정해봅시다. 그렇다면 위 상황은 1을 제외한 (N-1)명의 사람이 (N-1)개의 선물을 교환한 상황으로 바뀌며, 이 때 방법의 수는 DP[N-1]가 됩니다. 그리고, 1번 사람이 선물을 받게 되는 방법의 수는 (N-1)개 이기 때문에 나올 수 있는 총 경우의 수는 (N-1)*DP[N-1] 가 됩니다.

 

위의 수식들을 활용해 점화식을 만들면 다음과 같으며, 이를 활용하여 문제를 해결할 수 있습니다.

>> DP[N] = (N-1)*DP[N-1] + (N-1)*DP[N-2]

 

3. 소스코드

#include <stdio.h>
#define NMAX 1000010
#define MOD 1000000000
 
int N;
long long int dp[NMAX];
 
int main() {
    scanf("%d", &N);
 
    dp[0] = 1;
    for(int i=2;i<=N;i++) dp[i] = ( (i-1)*dp[i-2]%MOD + (i-1)*dp[i-1]%MOD )%MOD;
 
    printf("%lld", dp[N]);
}