백준 1947 - 선물 전달

icpc.me/1947

 

인문계 고등학교에서 경우의 수를 공부해봤다면 한 번쯤 봤을 법한 교란순열(완전순열)의 대표 예제임을 알 수 있다.

 

교란순열에 대해 배우지 않았다면 여기를 참조하자.

 

그때 그 시절, 아무래도 교란순열의 점화식은 알려주지 않았을지도 모른다. 하지만 우린 이 문제를 풀어야 하므로 점화식을 배우도록 하자.

 

교란순열의 점화식은 다음과 같다.

 

$D_n = (n - 1)(D_{n-1} + D_{n-2}) \ (D_0 = 1, D_1 = 0)$

 

동적계획법을 통해 점화식을 구현하도록 하자. 물론 오버플로우도 주의해주자.