취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1947번 문제인 선물 전달이다.

문제는 아래 링크를 확인하자.

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

이 문제는 교란순열(derangement)의 경우의 수인 교란수(derangement number; subfactorial)를 구하는 문제이다.

교란순열이란 1부터 n까지의 숫자를 i번째 숫자가 i가 되지 않게 나열한 순열을 의미한다.

n번째 교란수를 !n이라 표기하자. !n에 대하여 다음이 성립한다.

!0 = 1, !1 = 0, !n = (n-1)*(!(n-1)+!(n-2))  (단, n은 2 이상의 정수)

다음은 위 식이 성립하는 이유를 간단히 서술한 것이다.

n(>=2)개의 수를 n이 n번째에 오지 않게 일렬로 놓을 것이다. 이때 n은 n번째 위치에 있을 수 없으므로 k(<n)번째 위치에 놓게 된다. 이때 n번째 위치에는 (1)k가 오거나 (2)k가 오지 않을 것이다.

(1) n번째 위치에 k가 왔다면, 남은 수를 배치하는 경우의 수는 !(n-2)이다. n과 k의 위치만 서로 바뀐 것이므로 남은 수를 배치하는 경우의 수는 n개의 수 중 n과 k를 제외한 n-2의 숫자를 배치하는 문제로 바뀌기 때문이다.

(2) n번째 위치에 k가 아닌 다른 수가 오는 경우의 수를 구해보자. k번째 위치에는 n이 이미 채워져 있으므로 신경쓰지 말고 "n번째 위치"를 k번째 위치처럼 취급하면, 구하는 경우의 수는 1부터 n-1까지의 수를 "i번째 위치에 i가 오지 않게 나열하는 경우의 수"와 같다는 것을 알 수 있다. 이는 !(n-1)과 같다.

(1)과 (2)를 종합하면, n이 k(<n)번째 위치에 있는 교란순열의 개수는 !(n-1)+!(n-2)가 된다. 한편, k는 n이 아닌 모든 위치가 될 수 있으므로 k의 경우의 수는 n-1가지이다. 따라서 n번째 교란수는 (n-1)*(!(n-1)+!(n-2))로 구할 수 있다.

위 점화식을 이용하여 주어진 문제를 간단히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll dearr[1000001];

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

	dearr[0] = 1;
	for (ll n = 2; n < 1000001; n++) {
		dearr[n] = ((n - 1) * (dearr[n - 1] + dearr[n - 2])) % 1000000000;
	}

	int x; cin >> x;
	cout << dearr[x];
}