[백준] 13699번. 점화식

[백준] 13699번. 점화식

1. 문제

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:

t(0)=1
t(n)=t(0)t(n-1)+t(1)t(n-2)+...+t(n-1)*t(0)
이 정의에 따르면,

t(1)=t(0)t(0)=1
t(2)=t(0)t(1)+t(1)t(0)=2
t(3)=t(0)t(2)+t(1)t(1)+t(2)t(0)=5
...
주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.

3. 출력

첫째 줄에 t(n)을 출력한다.

4. 풀이

• 2차원 배열과 합계를 저장하는 배열 2개를 사용하여 풀었다.
• 2차원 배열에 각 항의 값을 저장하고 그 항의 합을 다른 배열에 저장하였다.
• 합을 저장하는 배열이 필요한 이유는 그 다음에 써야해서
• 합을 저장하는 배열이 t(n)이 된다.
• 마지막에 n에 해당하는 배열 값을 출력하면 된다.
• arr[i][j] = d[i - j -1] * d[j]
  점화식을 그대로 식으로 나타내었다.

5. 처음 코드와 달라진 점

• 위의 풀이를 먼저 생각하고 loop를 더 줄일 수 없을까 하다가 오히려 이상하게 접근했다.
• 파스칼 삼각형처럼 구할 수 있을 줄 알았다. 거기서 곱하기로 하면 될 줄...
  열심히 곱하다가 내가 감달할 수 없는 값이 나왔을 때 이상하다는 걸 느꼈다.
• 근데 파스칼 삼각형으로 했어도 어차피 2중 loop긴 했다.

6. 코드

#include <iostream>

using namespace std;

long long arr[36][36];
long long d[36];

int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int n;
    cin >> n;
    d[0] = 1;
    d[1] = 1;

    for (int i = 2; i <= 35; i++) {
        long long sum = 0;
        for (int j = 0; j < i; j++) {
            arr[i][j] = d[i - j -1] * d[j];
            sum += arr[i][j];
        }
        d[i] = sum;
    }
    cout << d[n];
}