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

[11726 2xn 타일링]

난이도: 실버3

11726번: 2×n 타일링

문제

입력

출력

---

[아이디어]

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

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

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

 

따라서 D[i] = D[i-1] + D[i-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] = 2;
		
		for(int i = 3; i <= N; i++) {
			D[i] = (D[i - 2] + D[i - 1]) % mod;
		}
		
		System.out.println(D[N]);
		
	}

}