[BOJ 13699 // C++] 점화식

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

 

이번에 볼 문제는 백준 13699번 문제인 점화식이다.
문제는 아래 링크를 확인하자.

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

13699번: 점화식

주어진 점화식을 반복문을 이용하여 그대로 구현해주자.

 

재귀적으로 작동하는 함수와 dp를 이용하여 문제를 해결해도 좋을 것이다.

 

답이 32비트 정수로 표현 가능한 범위를 넘을 수 있음에 유의하자.

 

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

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

ll N;
ll dp[36];

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

	dp[0] = 1;
	for (ll i = 1; i < 36; i++) {
		for (ll j = 0; j < i; j++) dp[i] += dp[j] * dp[i - j - 1];
	}

	cin >> N;
	cout << dp[N];
}