[백준-11727번] 2×n 타일링 2 풀이 - Java

🚀 문제

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

 

🚀 접근 방법

DP 문제이다.

총 종류가 3가지 이므로 

직전에서 1개가 늘어나면 2x1 타일밖에 오지 못해서 dp[i-1]

이전꺼에서 2개가 늘어나면 2가지 타입으로 올 수 있기 때문에 dp[i-2]*2따라서 점화식은 dp[i] = dp[i-1]+dp[i-2]*2가 된다.

 

🚀 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(in.readLine());
        final int MOD = 10007;

        int[] dp = new int[n+1];

        dp[1] = 1;
        if(n>=2)
            dp[2] = 3;

        for(int i=3; i<=n; i++){
            dp[i] = (dp[i-1]+dp[i-2]*2)%MOD;
        }

        System.out.println(dp[n]);
    }
}