백준 13699 점화식 문제풀이 (JAVA)

문제 링크

문제

---

다음의 점화식에 의해 정의된 수열 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)을 출력하는 프로그램을 작성하시오.

입력

---

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

출력

---

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

풀이

---

그냥 문제에서 하라는 대로 식을 짜면 된다.

• dp[i] += (dp[j] * dp[i - 1 - j]);
• j = 0 ~ (i -1)

소스코드

---

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        final int NUMBER = Integer.parseInt(br.readLine());
        long dp[] = new long[36];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < 36; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += (dp[j] * dp[i - 1 - j]);
            }
        }

        sb.append(dp[NUMBER]);
        sb.append("\n");
        bw.write(sb.toString());

        bw.flush();
        br.close();
        bw.close();

    }


}