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

1. 문제 링크

11727번: 2×n 타일링 2

 

2. 문제 및 입출력예제

 

 

3. 문제 풀이

앞서 올린 2xn 타일링을 응용한 예제이다.

2xN 타일링 문제와 시작은 똑같다.

대신 2x2 타일이 새로 생겨서 그 경우의 수를 알아야 한다.

 

그려 보니까 2개 이상 차이가 나는 경우에 2x2 타일을 추가할 수 있었다.

즉, a[i] = a[i-1] + a[i-2]*2라는 점화식이 나온다.

 

4. 코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		StringBuilder sb = new StringBuilder();
		int[] arr;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arr = new int[N];
		arr[0] = 1;
		if (N>1) {
			arr[1] = 3;
		}
		if(N>2) {
			arr[2] = 5;
		}
		
		for (int i=3; i<N; i++) {
			arr[i] = (arr[i-1] + 2*arr[i-2]) % 10007;
		}
		System.out.println(arr[N-1]);
	}
}