풀이
오랜만에 정상적인 풀이!!
더 자세히 알고 싶다면 구글에 완전순열 또는 교란을 검색해 보자!
증명
D[n] = (n-1) * (D[n-1] + D[n-2])
자연수 1~n에 n+1을 더해서 완전순열을 만들어 보자.
n+1은 1~n 중의 어떤 수 k의 자리에 놓인다.
이러한 k는 1부터 n까지 총 n개가 있을 수 있다.
그리고 우리는 이후의 상황을 다음의 두 경우로 나눌 수 있다.
1. n+1이 k의 자리에, k가 n+1의 자리에 놓이는 경우:
k와n+1을 제외한 나머지n-1개의 수로 완전순열을 만든다.- 이러한
k가 총n개가 있으므로 경우의 수는(n * D[n-1])
2. n+1이 k의 자리에, k가 n+1이 아닌 자리에 놓이는 경우:
n+1을 제외한 나머지n개의 수로 완전순열을 만든다.- 이러한
k가 총n개가 있으므로 경우의 수는(n * D[n])
위의 두 경우를 통해, D[n+1] = n * (D[n] + D[n-1]) 이라는 점화식을 얻어낼 수 있다.
휴 풀이 쓰기 힘들다
코드
#include <stdio.h>
const int mod = 1e9;
int n, i, a, b = 1, c;
int main() {
scanf("%d", &n);
for (i = 3; i <= n; i++) {
c = (long long)(i - 1) * (a + b) % mod;
a = b, b = c;
}
if (n == 1) puts("0");
else if (n == 2) puts("1");
else printf("%d", c);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이, 완전순열, 교란, 완전, 교란순열, complete permutation, derangement