BOJ13699_점화식

개요

동적 계획법(다이나믹 프로그래밍)의 핵심인 점화식에 대해 알아보고 코드를 구현해보자

점화식이란?

점화식은 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식이다.
-위키백과

동적계획법이란?

수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다
-위키백과

문제 접근

문제에서 제시하는 점화식을 다이나믹 프로그래밍으로 구현해보자
친절하게 점화식이 있으니 코드로 구현만 하면 된다

코드

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

public class Main{

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		long[] dp = new long[n + 1];
		dp[0] = 1;

		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= i; j++) {
				dp[i] += dp[i - j] * dp[j - 1];
			}
		}
		bw.write(dp[n] + "");
		bw.close();
	}
}