백준 알고리즘 11727번 2*N 타일링 2

동적계획법(Dynamic Programming)

타일을 구성할 수 있는 방법에 대해 재귀를 이용하여 Dp배열을 완성

항상 기준은 1,2, ... N 일때   i 번째를 기준으로 앞 쪽에 저장된 Dp값을 이용하면 된다.

static public void main(String args[]) throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());

        long[] dp = new long[N+1];

        System.out.println(solve(N,dp)%10007);
    }

    static long solve( int N, long[] dp)
    {
        if(dp[N] > 0)
        {
            return dp[N];
        }
        if(N == 0 )
        {
            return 1;
        }
        if(N >= 2)
        {
            long temp = solve(N-2,dp) * 2 + solve(N-1, dp);
            dp[N] += temp%10007;
        }
        else
        {
            long temp = solve(N-1,dp);
            dp[N] += temp%10007;
        }

        return dp[N];

    }