13699번. 점화식

 

아이디어

점화식 문제는 t(n) 의 값을 얻기 위해서 이전 값들인 t(0) ~ t(n - 1) 을 활용하는 문제이다.

 

t(i) 는 t(i + 1) ~ t(n) 까지의 계산에 모두 필요한데 매번 t(i) 를 계산하면 비효율적이므로 한 번 계산된 t(i) 값은 배열에 저장해뒀다가 다음에 필요할 경우 꺼내서 이를 사용하는 'DP' 방식을 활용해서 문제를 풀면 된다.

 

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        long[] t = new long[n + 1];
        t[0] = 1L;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i - 1; j++) {
                t[i] += t[j] * t[i - (j + 1)];
            }
        }

        System.out.println(t[n]);
    }
}