[java, 동적 계획법 dynamic programming]백준 11726번- 2 x n 타일링

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

11726번: 2×n 타일링

 

코드

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
 
        long[] D = new long[n + 1];
        D[0] = 1;
        D[1] = 1;
 
        if (n >= 2) {
 
            for (int i = 2; i <= n; i++) {
 
                D[i] = (D[i - 2] + D[i - 1]) % 10007;
 
            }
        }
 
        System.out.println(D[n]);
 
    }
}

 

---

풀이

D[i] 

 =끝이 1칸(1x2)으로 끝날 때 + 끝이 2칸(2x1)으로 끝날 때

 

끝이 1칸(1x2)으로 끝날 때= D[i-1]

 

끝이 2칸(2x1)으로 끝날 때= D[i-2]

 

점화식:

D[i] = (D[i - 2] + D[i - 1]) % 10007;