[백준 11727] 2×n 타일링 2

풀이

해설

n이 1일 때, 2x1타일 하나가 들어갈 수 있고, n이 2일 때 (1x2, 1x2), (2x1, 2x1), (2x2) 3가지 경우의 수로 타일을 채울 수 있다.

그리고 n이 3일 때를 보면,

 

2x1타일을 왼쪽이 위치시켰을 경우 n이 2일 때 경우의 수만큼 채우고,
n이 1일 때 경우의 수인 2x1타일이 2번 채워지는 것을 볼 수 있다.

 

n이 4일 경우에도 마찬가지이다.

 

이것을 이용해 점화식을 짜본다면, n = n-1 + (n-2) * 2가 나온다.

시간복잡도

• N만큼 순회하므로, O(N)이다.

코드

package _2xn타일링2_11727;

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

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

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

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

Reference

• 문제
• 참고