[백준 11727] 2xn 타일링 2 - 자바

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

11727번: 2×n 타일링 2

---

1. 풀이

[백준 11726 2xn 타일링] 와 거의 똑같은 문제이다.

 

하지만 조건에서 2x2의 타일도 가능하다했으므로 

 

점화식을 세워보면 D[n] = D[n-1] + D[n-2] + D[n-2]가 나오는 것을 볼 수 있다.

 

---

2. 코드

import java.util.*;

public class Main {

    static int[] memo = new int[1001];

    static int tile2(int n){
        if(memo[n] > 0)
            return memo[n];
        memo[n] = (tile2(n-1) + 2*tile2(n-2))%10007;
        return memo[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        memo[1] = 1;
        memo[2] = 3;
        int n = sc.nextInt();
        System.out.println(tile2(n));

        sc.close();
    }
}