코드 복사/붙여넣기 하는 당신이 아름답습니다.

1947 : 선물 전달

풀이

오랜만에 정상적인 풀이!!

더 자세히 알고 싶다면 구글에 완전순열 또는 교란을 검색해 보자!

증명

D[n] = (n-1) * (D[n-1] + D[n-2])

자연수 1~nn+1을 더해서 완전순열을 만들어 보자.

n+11~n 중의 어떤 수 k의 자리에 놓인다.

이러한 k1부터 n까지 총 n개가 있을 수 있다.

그리고 우리는 이후의 상황을 다음의 두 경우로 나눌 수 있다.

1. n+1k의 자리에, kn+1의 자리에 놓이는 경우:

  • kn+1을 제외한 나머지 n-1개의 수로 완전순열을 만든다.
  • 이러한 k가 총 n개가 있으므로 경우의 수는 (n * D[n-1])

2. n+1k의 자리에, kn+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

wookje.kwon's profile image

wookje.kwon

2018-01-25 00:16

Read more posts by this author