백준 BOJ 1947 - 선물 전달

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

1947번: 선물 전달

DP 문제 ( 수열의 유도 및 구현 )

개념을 알고 모르고의 유무로 난이도가 극명하게 갈린다고 할 수 있는 문제.

이 문제에서 요구하는 수열은 "교란순열" 혹은 "완전순열" 이다.

44라는 숫자가 나오면 한번쯤 의심해볼만할듯.

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

교란순열을 구하는 DP 점화식은 다음과 같다.

 

DP[i] : i명끼리 조건에 맞게 선물을 분배하는 경우의 수

 

유도

각각의 사람의 번호를 $a_i$ , 선물의 번호를 $b_i$ 로 둔다.

어떠한 사람 A가 선물을 하는 경우는 $(N-1)$ 가지이다.

이 각각의 상황에 대해서, 선물을 받은 사람을 A' 이라고 하면

 

1.  A와 A' 이 서로 선물을 주고받음.

이 경우에는 A와 A' 두사람을 제외한 N-2명의 사람에 대해서

또 사람 A를 뽑고 선물을 분배하는 과정을 반복하면 된다.

이러한 과정의 반복은 DP의 정의에 의해 DP[N-2] 와 같다.

 

2.  A'는 A에게 선물을 주지 않고 다른 사람에게 줌.

이 경우에는 A를 제외한 N-1명끼리 선물을 분배한 후

남은 단 한개의 선물을 A에게 주면 된다.

이 과정은 DP의 정의에 의해 DP[N-1] 이다.

 

1번과 2번 과정이 동시에 일어날 수 없으므로,

DP[N] 을 만드는 전체 경우의 수는 (N-1) * (DP[N-1] + DP[N-2]) 이다.

수 범위가 커질 수 있으므로 long long 형으로 선언해줄것

 

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

ll dp[1234567] = {0};

int main(){
	dp[0] = 0;
	dp[1] = 0;
	dp[2] = 1;
	for(int i=3; i<=1000000; i++){
		dp[i] = (dp[i-1]+dp[i-2])*(i-1) % 1000000000LL;
	}
	
	int N;
	cin >> N;
	cout << dp[N];
	
	return 0;
}