[BOJ 18132 // C++] 내 이진트리를 돌려줘!!!

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

 

이번에 볼 문제는 백준 18132번 문제인 내 이진트리를 돌려줘!!!이다.
문제는 아래 링크를 확인하자.

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

18132번: 내 이진트리를 돌려줘!!!

에지가 하나 이상 있는 트리는 (1)루트에 자식이 하나 있거나 (2) 루트에 자식이 두개 있는 두가지 경우중 정확히 하나를 만족함을 관찰하자.

 

위의 관찰을 이용하면 루트의 자식 하나 또는 둘을 루트로 갖는 서브트리의 경우의 수를 이용해 점화식을 세워 문제를 해결할 수 있다.

 

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

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

int T;
ll dp[5001];

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

	dp[0] = 1, dp[1] = 2;
	for (ll n = 2; n < 5001; n++) {
		dp[n] = dp[n - 1] * 2;
		for (ll m = 0; m < n - 1; m++) {
			dp[n] = (dp[n] + dp[m] * dp[n - m - 2]) % MOD;
		}
	}

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