백준 1670 정상회담 2

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

1670번: 정상 회담 2

 

다이나믹 프로그래밍 문제

 

점화식은

 

f(n) = { f(n-2) * f(0) } + { f(n-4) * f(2) } + ... + { f(k - m) * f(m-2) } + ... + { f(0) * f(n-2) }다.

 

예를 들어서

f(4) = f(2) * f(0) + f(0) * f(2)

f(6) = f(4) * f(0) + f(2) * f(2) + f(0) * f(4)

 

이다.

 

그림을 보며 이해해보자 .

 

네 명의 악수 선을 그으면 왜 저런 점화식이 나오는 지 이해할 수 있다. 

 

 

여섯명의 악수 이것도 선을 그어보면 이해할 수 있다.

여섯명짜리 악수를 대표로 살펴보자

 

 

이렇게 세 가지 경우가 나올 수 있다. 

8개 짜리도 해보면 재밌을듯...

 

import java.io.*;
import java.util.StringTokenizer;

public class boj1670 {

    static long[] dp = new long[10010];

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N;
        N = Integer.parseInt(st.nextToken());
        dps(N);
        bw.write(dp[N] + "\n");
        bw.flush();
    }

    static void dps(int N) {
        dp[0] = 1;
        dp[2] = 1;
        for(int i = 4; i <= N; i += 2){
            long temporalSum = 0;
            for(int j = i-2; j >= 0; j -=2){
                temporalSum += ((dp[j] * dp[i - 2 -j]) % 987654321);
                temporalSum %= 987654321;
            }
            dp[i] = temporalSum;
        }
    }
}