백준(BOJ) 13699 점화식 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/13699

13699번: 점화식

풀이에 이용된 알고리즘: DP

 

문제를 읽고 시그마 기호를 이용한 점화식을 간단히 작성 후 코드로 옮기면 되는 굉장히 간단한 문제이다!!!!!

 

그리고 점화식에서 t(n)을 계산할 때 t(n-1), t(n-2), t(n-3)... 등 n보다 작은 입력 값의 결과들이 이용된다. --> 누가봐도 dp를 활용해야할 것 같은 문제이다.

 

하지만 아주 한가지 미세하지만 정말 중요한 고려 사항이 있는데, n 값이 커질 수록 점화식의 결과 t(n)이 엄청나게 커진다는 것이다.

 

보통 int 자료형을 많이 이용할텐데 엄청나게 큰수 2^31 이상의 수는 표현할 수 없고 overflow가 발생한다.

 

따라서 long long 타입의 dp 배열을 생성하여 연산할 수 있도록 하자.

 

/* BOJ 13699 점화식 */
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int n;
ll dp[36];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n;
 
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int k = 1; k <= i; k++)
            dp[i] += dp[k - 1] * dp[i - k];
 
    cout << dp[n] << endl;
 
    return 0;
}