백준 - 11726 [2xn 타일링]

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

문제 풀이 

 

마지막이 항상 세로 타일 1개 또는 가로 타일 2개가 올 수 있다.

세로 타일이 왔을 경우는 세로 타일의 길이를 제외하면 n-1,

가로 타일이 왔을 경우는 가로 타일의 길이를 제외하면 n-2 이다.

마지막에 올 수 있는 타일의 형태에 따라 앞의 n-1 또는 n-2의 타일의 경우의 수는 

앞에 구해놓은 dp에서 가져오면 된다.

따라서 점화식을 dp[n] = dp[n-1] + dp[n-2] 로 만들 수 있다.

 

 

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] d = new int[1001];
        d[1] = 1;
        d[2] = 2;
        for(int i=3; i<=n; i++)
            d[i] = (d[i-1] + d[i-2])%10007;
        System.out.println(d[n]);
        in.close();
    }
}