[PS] 백준 11726번 2×n 타일링 - DP

문제

예제

풀이

경우의 수를 따지면 1,2,3,5,8 ... 이렇게 결과가 나오는데, 방법은 2가지가 있다.

1. 피보나치 수열로 푸는 방법
2. 사각형을 그렸을 때의 경우의 수를 점화식으로 푸는 방법

2번의 경우 아래 그림에 따라

점화식 dp[n] = dp[n-1] + dp[n-2] 이 적용되는 것을 사용하는 거다.

주의할 점은 dp[n]의 값을 저장할 때 마다 10007로 나눈 값을 저장해야한다.
조건에서 n은 1000까지 커질 수 있는데,
결과가 출력할 때 나누면 특정 n을 넣었을 때 int 타입의 범위인 2^31승 약 열자리를 넘기때문이다.

코드

import java.util.Scanner;

public class Main {

    static Integer[] dp;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        dp = new Integer[N+1];
        dp[0] = dp[1] = 1;

        System.out.println(caculate(N));

    }

    static int caculate(int n) {

        if(dp[n] == null) {
            dp[n] = (caculate(n-1) + caculate(n-2)) % 10007;
        }
        return dp[n];
    }
}