BOJ 1904번 01타일

package BOJ.DP;

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

/**
 * BOJ 1904
 * https://www.acmicpc.net/problem/1904
 */
public class _01Tile_1904 {

    private static int[] arr;

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

    // D(n) : 길이가 n인 2진수열의 갯수
    // D(n)의 마지막 자리에 '00'이 오는 경우와 '1'이 오는 경우 2가지가 있다.
    // D(n) = D(n-2) + D(n-1)
    private static int solve(int n) {
        if(arr[n] > 0)
            return arr[n];

        arr[n] = solve(n-1) + solve(n-2);
        arr[n] %= 15746;
        return arr[n];

    }
}