[BOJ 10978 // C++] 기숙사 재배정

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

 

이번에 볼 문제는 백준 10978번 문제인 기숙사 재배정이다.

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

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

10978번: 기숙사 재배정

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

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

 

교란수수를 구하는 점화식은 여러가지가 있지만 여기서는 N의 제한이 작으므로 생각해내기 쉬운 형태의 식으로 문제를 해결해보자.

 

n-1까지의 교란수를 모두 알고 있을 때 n번째 교란수를 구해보자.

1부터 n까지의 수를 아무렇게나 나열하면 0, 1, ..., n 중 하나의 개수만큼 순열 "1 2 ... n"과 일치하게 된다.

이중 하나의 수가 일치할 경우의 수는 1개의 일치할 수를 고르고 나머지 n-1개의 수들이 모두 겹치지 않게(n-1번째 교란수) 배치하는 경우의 수로 계산할 수 있다.

마찬가지로, k개의 수가 일치할 경우의 수는 k개의 일치할 수를 고르고 나머지 n-k개의 수들이 모두 겹치지 않게(n-k번재 교란수) 배치하는 경우의 수로 계산할 수 있다.

 

n!에서 1 이상 n 이하의 k개의 수가 일치할 경우의 수를 전부 빼주면 남는 값이 n번째 교란수가 된다.

 

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

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

ll comb[21][21];
ll dearr[21];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	dearr[0] = 1;
	for (ll i = 1; i < 21; i++) dearr[i] = dearr[i - 1] * i;

	for (int i = 0; i < 21; i++) comb[i][0] = 1;
	for (int i = 1; i < 21; i++) {
		for (int j = 1; j <= i; j++) {
			comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
		}
	}

	dearr[0] = dearr[2] = 1, dearr[1] = 0;

	for (ll n = 3; n < 21; n++) { // 현재 dearr[n] = n! (n>=3)
		for (int k = 1; k <= n; k++) { // n명중 k명 일치 경우의 수 제거
			dearr[n] -= comb[n][k] * dearr[n - k];
		}
	}

	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		cout << dearr[x] << '\n';
	}
}