[백준][11726번] 2xn 타일링

문제 URL

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

나의 풀이

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

public class Main {
    public static int[] d;

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

    public static int cal(int n) {
        if (n <= 1)
            return 1;
        if (d[n] > 0)
            return d[n];
        return d[n] = (cal(n - 1) + cal(n - 2)) % 10007;
    }
}

느낀점

동적계획법 을 이용한 문제다.

가장 오른쪽 타일이 놓을 수 있는방법이 총 2가지있다. 따라서, 점화식은 D[n] = D[n-1] + D[n-2] 이다.