완전순열 (1) 썸네일형 리스트형 백준 1947 - 선물 전달 icpc.me/1947 인문계 고등학교에서 경우의 수를 공부해봤다면 한 번쯤 봤을 법한 교란순열(완전순열)의 대표 예제임을 알 수 있다. 교란순열에 대해 배우지 않았다면 여기를 참조하자. 그때 그 시절, 아무래도 교란순열의 점화식은 알려주지 않았을지도 모른다. 하지만 우린 이 문제를 풀어야 하므로 점화식을 배우도록 하자. 교란순열의 점화식은 다음과 같다. $D_n = (n - 1)(D_{n-1} + D_{n-2}) \ (D_0 = 1, D_1 = 0)$ 동적계획법을 통해 점화식을 구현하도록 하자. 물론 오버플로우도 주의해주자. 이전 1 다음