백준 11727번 - 2xn 타일링2 (Java 8)

 

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

11727번: 2×n 타일링 2

코드 :

dp, 탑다운

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] tiles;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        tiles = new int[n + 1];
        tiles[0] = 1;
        tiles[1] = 1;

        System.out.println(tile(n));
    }

    public static int tile(int n){
        if(tiles[n] != 0) {
            return tiles[n];
        }
        tiles[n] = (tile(n - 1) + 2 * tile(n - 2)) % 10007;
        return tiles[n];
    }
}

직접 그려보면, 두칸짜리 네모가 생기면서, f(n) = f(n-1) + 2*f(n-2)가 되었다.