[C++] BOJ(백준) 1947 선물 전달

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

1947번: 선물 전달

dp 문제다.

완전 순열로 본인이 본인 것을 선택하는 경우를 제외한 순열이다.

 

n = 2인 경우 a - 2, b - 1 이렇게 한 가지 경우다.

 

n = 3인 경우

a - 2, b - 3, c - 1

a - 3, b - 1, c - 2

이렇게 두 가지 경우다.

 

n = 4인 경우

a - 2, b - 3, c - 4, d - 1

a - 2, b - 4, c - 1, d - 3

a - 2, b - 1, c - 4, d - 3

a - 3, b - 1, c - 4, d - 2

a - 3, b - 4, c - 1, d - 2

a - 3, b - 4, c - 2, d - 1

a - 4, b - 1, c - 2, d - 3

a - 4, b - 3, c - 1, d - 2

a - 4, b - 3, c - 2, d - 1

이렇게 9가지 경우다.

 

n = 5인 경우 44가지다.

 

점화식

Dn = (n - 1)(Dn-1 + Dn-2), n >= 2, D0 = 1, D1 = 0

점화식을 알면 바로 DP를 적용할 수 있다.

#include <iostream>
using namespace std;

long long n, dp[1000001] = { 1, 0 };

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

	cin >> n;
	for (int i = 2; i <= n; i++)
		dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % 1000000000;
	cout << dp[n];
}