취미로 코딩하기

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

이번에 볼 문제는 백준 9457번 문제인 기하학문양이다.
문제는 아래 링크를 확인하자.

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

먼저 $R_n$부터 계산해보자.

우선 $R_1=1$임은 자명하다. n이 2 이상인 경우를 생각할 때, 주어진 그리드는 n이 1 작은 경우의 그리드의 오른쪽에 노드 2개와 에지 3개를 추가해 만든 그리드와 같은 모양임을 관찰하자.

이와 같은 그리드의 스패닝 트리들은 맨 오른쪽의 두 노드 및 연결된 에지를 삭제했을 때 n이 1 작은 경우의 스패닝 트리가 되거나 되지 않는 두 가지로 분류할 수 있다. 전자의 경우 n이 1 작은 경우의 스패닝 트리에 오른쪽의 에지 3개 중 2개를 고르는 경우의 수를 곱한 개수만큼 존재한다. 후자의 경우, 오른쪽의 에지 3개가 모두 스패닝 트리에 포함된 경우이고, 그 개수는 그리드의 윗변과 아랫변이 모두 존재하는 연속(contiguous)한 길이가 얼마냐에 따라 각각 그 값을 계산해낼 수 있음을 관찰할 수 있다. 다음 그림은 그리드의 오른쪽 끝부터 윗변과 아랫변이 모두 존재하는 연속한 최대 길이가 2인 스패닝 트리 중 하나의 일부를 나타낸 것으로, 이 모양을 포함하는(오른쪽에서 세번째 윗변이 포함되지 않음) 스패닝 트리의 개수는 $R_{n-3}$과 같음을 확인할 수 있다.

위에서 구한 관계를 이용해 $R_n$을 구해내는 점화식을 세우자. 이 때, 식을 잘 정리하면 $R_1$부터 $R_n$까지의 모든 값을 prefix sum을 이용해 $O(n)$에 구해낼 수 있음을 확인하자.

$C_n$의 경우, 각 스패닝 트리에 대하여 원의 바깥쪽에서 안쪽으로 스패닝 트리에 포함되는 에지와 교차하지 않으면서 이동할 수 있는 방법이 유일함(방법이 둘 이상이면 스패닝 트리가 connected하지 않게 됨을 관찰하자.)을 이용해 바깥쪽에서 들어가는 위치와 안쪽으로 나오는 위치를 정했을 때의 경우의 수를 각각 구해 문제를 해결하자. 이를 계산할 때 $R_n$의 값을 구할 때와 유사하게 prefix sum을 이용하여 최적화하면 $O(n)$에 $n$ 이하의 모든 $C_n$의 값을 구할 수 있다.

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

#define MOD 10007LL
#include <iostream>
using namespace std;
typedef long long ll;

ll R[50001], rsum;
ll C[50001], csum = 1;
int T, N;

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

	R[1] = 1;
	for (ll i = 2; i < 50001; i++) {
		R[i] = (R[i - 1] * 3 + rsum * 2 + 1) % MOD;
		rsum = rsum + R[i - 1] % MOD;
	}

	C[1] = 1;
	for (ll i = 2; i < 50001; i++) {
		C[i] = (i * R[i] + i * 2 * csum) % MOD;
		csum = (csum + R[i]) % MOD;
	}

	cin >> T;
	while (T--) {
		cin >> N;
		cout << R[N] << ' ' << C[N] << '\n';
	}
}