[Algorithm Study] 백준 11726

문제 출처 : https://www.acmicpc.net/problem/11726

문제 접근

2XN 타일링 문제는 다이나믹 프로그래밍 알고리즘의 문제로 풀이 방식이 top-down과 bottom-up방식이 있습니다. 이 문제는 bottom-up 방식으로 문제를 해결 했습니다.
(bottom-up은 점화식을 이용하는 방식입니다.)
n == 1 인 경우에 타일을 깔 수 있는 경우의 수는 1가지
n == 2 인 경우에 타일을 깔 수 있는 경우의 수는 2가지
n == 3 인 경우에 타일을 깔 수 있는 경우의 수는 3가지
n == 4 인 경우에 타일을 깔 수 있는 경우의 수는 5가지
즉, n이 1 또는 2를 제외한 타일을 까는 경우의 수는 (n-1)의 타일링 경우의 수 + (n-2)의 타일링 경우의 수 입니다.
이를 코드로 작성하면 아래와 같습니다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_11726 {
    static int[] dt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        dt = new int[1001];
        System.out.println(dp(N));
    }
    public static int dp(int N){
        if(dt[N] != 0) return dt[N];
        if(N == 1) return 1;
        if(N == 2) return 2;
        return dt[N] = (dp(N-1) + dp(N-2)) % 10007;
    }
}