[백준] S4 13699번 점화식 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

13699번: 점화식

[문제] 

다음의 점화식에 의해 정의된 수열 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)을 출력한다.

---

[풀이]

1. dp 배열을 만들어 준다.

2. 점화식을 사용해 dp배열에 값을 채워준다.

3. n에 해당하는 값을 출력한다.

[접근]

1. 점화식을 세워 해당 식에 대해 DP를 사용하여 문제를 해결하였다.

2. 점화식 : dp[i] += dp[j] * dp[i - 1 - j]

[코드]

import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = 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]);
                }
            }
            System.out.println(dp[n]);
	}
}