취미로 코딩하기

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

이번에 볼 문제는 백준 13912번 문제인 외계 생물이다.
문제는 아래 링크를 확인하자.

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

H일째의 외계 생물 2^(H+1) - 1 마리에게 이름을 붙여보자. 이를 dp[H]라 하겠다.

맨 처음에 새끼를 낳은 외계 생물은 유일하고, 해당 생물이 1번 번호를 달아야 함은 자명하다.

1번 번호의 생물은 두 마리의 새끼를 낳을 것이고, 각 새끼는 남은 H-1일동안 2^H - 1마리의 외계 생물을 생산해내게 될 것이다. 각 2^H - 1마리에게 달 번호로 사용할 수의 집합이 정해지면, 2^H - 1마리들에게 번호가 달릴 경우의 수는 dp[H-1]과 같게 됨을 관찰할 수 있다. 따라서 dp[H] = choose(2^(H+1) - 2, 2^H - 1) * dp[H-1]^2 로 계산할 수 있게 된다.

위 계산에 필요한 조합값은 O(N^2)에 미리 전처리해 구해두자.

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

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

int choose[2049][2049];

void combinit() {
	for (int n = 1; n < 2049; n++) {
		choose[n][0] = 1;
		for (int i = 1; i < n; i++) {
			int& cur = choose[n][i];
			cur = choose[n - 1][i - 1] + choose[n - 1][i];
			if (cur > 1000000006) cur -= 1000000007;
		}
		choose[n][n] = 1;
	}
}

ll ans[11];

void solve() {
	ans[0] = 1;
	for (int i = 1; i < 11; i++) {
		int tmp = (1 << (i + 1)) - 2;
		ans[i] = (choose[tmp][tmp / 2] * ((ans[i - 1] * ans[i - 1]) % 1000000007)) % 1000000007;
	}
}

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

	combinit();
	solve();

	int H; cin >> H;
	cout << ans[H];
}