[백준] 13699번: 점화식_java

https://www.acmicpc.net/problem/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)을 출력한다.

📎코드

import java.util.Scanner;

//t(n)=Σ{t(i)*t(n-i-1)}	(i=0 ~ i=n-1}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] t = new long[n+1];
        t[0]=1;
        for(int i=1;i<=n;i++){
            int j=0;
            do{
                t[i]+=t[j]*t[i-j-1];
                j++;
            }while(j<=i-1);
        }
        System.out.println(t[n]);
    }
}

📎코드 설명

코드의 주석처럼 점화식으로 나타내도록 하였다.
do~while문을 사용한 이유는 t(1)을 구하기 위함이다.
문제에 나와있듯이 t(0)이 주어진 조건이고 t(1)은 구해야 하는 점화식 중 하나이다.