BOJ11726 2 x n 타일링

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

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

점화식

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

최종 제출 코드

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

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

import java.util.Scanner;

public class BOJ11726 {

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

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

        for (int i = 1; i <= n; i++) {
            if (i == 1) {
                dp[i] = 1;
            } else if (i == 2) {
                dp[i] = 2;
            } else {
                dp[i] = dp[i - 1] + dp[i - 2] % 10007;
            }
        }

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

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