BOJ 10978 - 기숙사 재배정

그래프 이론 + dp 문제의 다소 신기한 문제라 포스팅한다.

i가 3이상인 구간에 대해서 아래의 공식이 성립한다.

아래 그림을 보자. 먼저 dp[i-1]을 설명한다.

< k->i이지만 i->k가 아닌 경우 >

0 <= k < i인 k에 대해 k와 i를 연결했다고 가정해보자. 그러면 나머지 연결되지 않은 i-1개의 정점에 대해서 서로 재배정이 되지 않도록 연결되어 있어야 한다. 이는 이미 dp[i-1]을 구했으므로 이를 이용한다. 또한 k의 후보는 0부터 i-1이므로 총 i개다. 따라서 i*dp[i-1]으로 나타낼 수 있다. 파랑색 평행사변형 안에 있는 k와 i의 정점을 "같다"고 판단한다. 즉 i->k로 가는 경우는 없이 세는 것이다.

< k->i이고 i->k인 경우 >

마찬가지로 k의 후보는 0~i-1이므로 총 i개, k에 대해 i를 연결하고 i에 대해 k를 연결하면 나머지 i-2개에 대해 재배정이 되지 않도록 하는 방법의 수는 dp[i-2]가 된다. 따라서 i*dp[i-2]가 된다.

이 이후로 사이클 3개, 4개에 대해서 다루지 않는 이유는 이미 dp[i-1]에 포함되어 있기 때문이다. k가 i를 가리키고 있는 와중에 나머지 i-1개의 정점들 간의 재배정되지 않는 경우 안에 이 것이 포함되기 때문에 버린다.

#include <cstdio>
int main() {
	int T, N;
	long long cache[21] = {};
	scanf("%d", &T);
	cache[1] = 1;
	for (int i = 2; i < 21; i++)
		cache[i] = i*(cache[i - 1] + cache[i - 2]);
	while (T--) {
		scanf("%d", &N);
		printf("%lld\n", cache[N-1]);
	}
	return 0;
}