BOJ11727 2 x n 타일링 2

https://www.acmicpc.net/problem/11727 (opens new window)

2 x n 직사각형을 1 x 2, 2 x 1, 2 x 2 타일로 채우는 방법의 수를 구한다.

점화식

이전 문제와 가장 큰 차이는 2 x 2 타일이라는 추가적인 경우가 늘어난 것이다. n - 1 까지의 타일 개수에서 2 x 1 타일을 붙이는 방법과 n - 2 까지의 타일 개수에서 1 x 2 타일 두개, 2 x 2 타일 한개를 더 붙일 수 있는 경우가 늘어났다. 그렇기 때문에 n - 2까지의 타일 개수에 x 2을 처리하여 점화식을 수정한다.

n = 1 이면 f(n) = 1
n = 2 이면 f(n) = 3
n >= 3 이면 f(n) = f(n - 1) + (f(n - 2) * 2)

최종 제출 코드

출력 결과는 10,007로 나눈 나머지이다. 주의해서 처리해야 한다.

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ11727 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] dp = new int[1001];

        dp[1] = 1;
        dp[2] = 3;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1]+ (dp[i - 2] * 2)) % 10_007;
        }

        System.out.println(dp[n]);
    }
}

#algorithm #BOJ #다이나믹 프로그래밍