[자바] 백준 13699 - 점화식 (java)

 문제 : boj13699

---

 

필요 알고리즘 개념

• 다이나믹 프로그래밍 (동적 계획법, DP)
  
  • DP 문제이긴한데, 그냥 memoization 문제라고 보면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  t(n)을 계산하기 위해서는 t(0)부터 t(n-1) 까지의 계산 결과가 모두 필요한데, 이걸 매번 점화식대로 구해주면 당연히 시간초과가 될 것이다. 그러니 매번 x = 1부터 35까지 t(x)를 순서대로 계산해주고, t(x)를 배열에 기록해준다(memoization). 그렇게 미리 t(1)부터 t(35)까지를 구한 뒤, n을 입력받아 t(n)을 출력해주면 된다.

 

---

 

코드 : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    long[] answer = new long[36];

    private void f(int n) {
        long cur = 0;
        for (int i = 0; i < n; i++) {
            cur += answer[i]*answer[n-1-i];
        }
        answer[n] = cur;
    }

    private void solution() throws Exception {
        answer[0] = 1;
        for (int i = 1; i <= 35; i++) {
            f(i);
        }
        System.out.println(answer[Integer.parseInt(br.readLine())]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}