[백준] 2482번 색상환 (gold 3

위의 문제는 다음과 같은 규칙을 가지는 것을 발견했다. 이문제는 점화식이 세워지는 다이나믹 프로그래밍 문제였던 것이다.

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.valueOf(br.readLine());
        int k=Integer.valueOf(br.readLine());
        //나누는 수
        int div=1000000003;
		//틀린 이유... 못구하는 케이스가 들어있다. 
        if(k>n/2){
            System.out.println("0");
        }
        else {
            //누적합 할 행렬을 만든다.
            int col = n;
            int row = n / 2;

            int[][] sum = new int[row + 1][n + 1];
            //첫 행 초기화.
            for (int i = 2; i <= n; i++) {
                sum[1][i] = i;
            }

            int index = 4;
            //가장 첫 인덱스가 두 칸씩 밀리며, 그 배열의 값은 바로 전 배열의 값과.
            //전 행, -2열의 배열 값을 합한 것과 같다. 
            for (int i = 2; i <= row; i++) {
                for (int j = index; j <= n; j++) {
                    sum[i][j] = (sum[i][j - 1] + sum[i - 1][j - 2]) % div;
                }
            }

            System.out.println(sum[k][n]);
        }

    }
}