/ BOJ

BOJ_11727_2xN타일링2_JAVA

문제 : 2xN타일링2

링크 : BOJ_11727_2xN타일링2

접근 방식

2xN 타일링에 이어서 생각해볼 수 있다.

2xN 타일링에서, 큰 사각형이 추가되었다는 뜻은, 세로로 2개, 가로로 2개 이어져있는 타일을 큰 사각형으로 바꿔치기 할 수 있다는 뜻이다.

N-1은 한 개의 타일이 들어갈 공간이 추가될 경우,

N-2는 두 개의 타일이 들어갈 공간이 추가될 경우를 뜻한다. 2x2의 큰 사각형이 들어갈 수 있느 경우는 N-2의 경우이므로, dp[N-1] + dp[N-2]*2를 구해주면 된다.

다른 관점으로는 이러한 것도 있다.

2개의 블럭이 들어갈 수 있는 공간에는, 1개의 타일을 2개 놓는 방법과 2x2 타일 1개를 놓는 방법 2가지의 경우의 수로 나뉠 수 있다 그렇기 때문에 dp[N-2] 구간에서 * 2를 해준다.

소스 코드

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

public class BOJ_11727_2xN타일링2 {
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());

		int dp[] = new int[N];

		if (N == 1) {
			System.out.println(1);
			return;
		}

		dp[0] = 1;
		dp[1] = 3;

		for(int i=2;i<N;i++) {
//			if(i%2 == 0) {
//				dp[i] = dp[i-1] + dp[i-2]*2;
//			}else {
//				dp[i] = dp[i-1]*2 + dp[i-2];
//			}
			dp[i] = (dp[i-1] + dp[i-2]*2)%10007;
		}

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

}