[백준] 11727 2xn 타일링2 (Java)

[11727 2xn 타일링2]

난이도: 실버3

11727번: 2×n 타일링 2

문제

입력

출력

---

[아이디어]

지금 문제를 풀기 전에 이 문제를 풀고 오는 것이 더 이해하기 쉽다.

[백준] 11726 2xn 타일링 (Java)

 

D[i] = 2 x i 의 직사각형을 채우는 방법 이라고 정하자.

2 x 1 의 크기의 블럭을 놓은 경우 2 x (n - 1) 크기의 블럭을 채워야한다.

1 x 2 크기의 블럭은 2개를 같이 놓는 방법뿐이다. 이 때 2 x (n - 2) 크기의 블럭을 채워야한다.

2 x 2 크기의 블럭 1개를 놓으면 2 x (n - 2) 크기의 블럭을 채워야한다.

2 x (n - 2) 크기의 블럭을 채우는 방법이 두가지이므로 D[i] = D[i-1] + D[i-2] * 2 의 점화식이 나온다.

---

[JAVA 코드]

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	static int N, mod = 10007;
	static int [] D;

	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		D = new int [N + 1];
		
		if(N == 1) {
			System.out.println(1);
			return;
		}
		
		D[1] = 1;
		D[2] = 3; // 1*2 두개, 2*1 두개, 2x2 한개 => 총 3개
		for(int i = 3; i <= N; i++) {
			D[i] = (D[i - 1] + 2 * D[i - 2]) % mod;
		}
		
		System.out.println(D[N]);
	}

}