[백준] 알고리즘 13699번 - 점화식 문제

문제

www.acmicpc.net/problem/13699

13699번: 점화식

소스코드

#include <bits/stdc++.h>
using namespace std;
long long dp[36];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	dp[0] = 1, dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		int flag = 1;
		for (int j = 0; j < i; j++) {
			dp[i] += dp[j] * dp[i - flag];
			flag++;
		}
	}
	cout << dp[n];
}

풀이

문제에 나와있는 식을 그대로 코드화 시켜주면 간단하게 해결할 수 있다.

다만 int 형으로는 초과하니 long long 을 써준다.