[JAVA]백준 13699번 문제 풀이

# 문제 출제 사이트

https://www.acmicpc.net/problem/13699

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;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        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]);
    }
}

 

 

# 참고자료

• 벨로그 phjppo0918.log => 링크
• 벨로그 블록체인 왕초보 입문기 => 링크

 

 

# 풀면서 느낀점 및 공부해야 할 것들

• 공식이 나와있는것을 코드로 옮기는 능력이 부족하다.
• 수학에대한 기본적인 지식이 너무 부족하고 학습하는 속도가 너무 느리다.
• 혼자서 직접 풀어보고 해당 문제를 이해할 수 있도록 다양한 영상과 개념을 찾아서 글로 정리해보자.
• 문제를 풀기전에 우선 노트에 내용을 정리해보기.
• 문제를 풀지 못했다면 풀이를 보면서 한단계 한단계 어떻게 돌아가는지 직접 보기(노트 작성)
• 공부해야 할 것들
  1. 피보나치 수열이란?
  2. 점화식이란?
  3. 재귀함수란?