[DP/자바] 코드트리 IL. 사각형 채우기 2

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 해석

이 문제도 전형적인 타일 깔기 문제라서 DP로 풀 수 있으며, 이는 매우매우 간단한 점화식으로 표현할 수 있다. 문제 조건에 등장하는 타일을 가지고 n의 길이를 가진 사각형을 채우는 경우의 수는 아래와 같이 점화식을 세울 수 있다.

 

f(n) = f(n-1) + 2 * f(n-2)

이를 참고하여 타뷸레이션 방식으로 DP 로직을 구성하면 아래와 같다.

 

 

문제 풀이

package 코드트리.DP;

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

public class 사각형_채우기_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[1001];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 3;
        for (int i = 3; i <= 1000; i++) {
            dp[i] = (dp[i - 1] + (2 * dp[i - 2]) % 10007) % 10007;
        }
        System.out.println(dp[n]);

    }
}