[BOJ] 11727 2xn타일링 2 - JAVA

1. 문제

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

11727번: 2×n 타일링 2

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

---

2. 풀이

규칙

• 변형된 2xn타일링 문제다. 
• N=2일때의 경우의 수가 한 개 늘어남에 따라 나머지 경우의 수들도 전부 영향을 받았다.
• N을 N-1의 경우의 수+ N-2의 경우의 수로 표현하는 골격은 비슷하지만 N-2의 앞에 붙일 수 있는 게 두 가지라 2*(N-2경우의 수)가 되었다.
• 설명보다 그림이 더 이해가 쉬울 것 같다.

코드

import java.io.*;

public class BOJ_11727_2xn타일링2 {
	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
		int DIV = 10007;

		int[] dp = new int[1000];
		dp[0] = 1;
		dp[1] = 3;

		for(int i=2;i<N;i++) dp[i] = (dp[i-1]+(dp[i-2]*2)%DIV)%DIV;

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

---

3. 결과