BOJ_13699 : 점화식

👉 문제링크

13699번: 점화식

---

---

🔸 문제 분석 🔸

• 점화식으로 배열을 채우는 dp 문제이다.
  • arr[0] = 1
  • arr[n] = arr[0]*arr[n-1] + arr[1]*arr[n-2] + ... + arr[n-1]*arr[0]

🔸 코드 🔸

import java.util.Scanner;

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

        for (int i = 1; i <= n; i++) {
            arr[i] = 0;
            for (int j = 0; j < i; j++) {
                arr[i] += arr[j]*arr[i-1-j];
            }
        }
        System.out.println(arr[n]);
    }
}

🔸 코드 해석 🔸

• dp배열의 크기는 0~n 까지이므로 n+1개로 선언한다.
  • 자료형은 예제 2번의 출력이 4861946401452으로 int를 초과하므로 long으로 선언한다.
• 채워야 하는 dp배열의 인덱스는 1부터 n까지이므로 첫 반복문에서 i를 1~n로 순회한다.
  • 다음 한 인덱스(arr[i])를 채우는 방법은 i번 반복하는 것이다.
  • arr[i]의 초기값으로 0을 넣는다.
  • j를 0~i-1 로 i번 반복해서 dp배열의 값을 채운다.

---

🔸 end 🔸

• dp문제의 점화식을 잘못 이해해서 코드를 다시 뜯어고쳐서 풀었다. 문제 자체는 어렵지 않았다.