11727번(2xn타일링2)

첫 시도

• 11726번(2xn 타일링)에서 업그레이드 된 문제이다.
• 원래 사용할 수 있는 타일은 2x1, 1x2 뿐이었는데 2x2 타일이 추가되면서 경우의 수가 추가되었다.
• 기존 2칸을 차지했던 곳에 2x2 타일이 들어갈 수 있기 때문에 경우의 수가 2배가 된다. 따라서 dp[i-2]*2 + dp[i-1]로 해결할 수 있다.

해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+1];
        if(N == 1){
            System.out.println(1);
            return;
        }
        dp[1] = 1;
        dp[2] = 3;


        for(int i = 3; i<N+1; i++){
            dp[i] = (dp[i-2]*2 + dp[i -1])%10007;
        }
        System.out.println(dp[N]);

    }
}

참고

• 직접구현