[Java] BOJ 11727번 2xn 타일링 2

11727번: 2×n 타일링 2

---

풀이

DP를 사용해서 해결했습니다.

 

직접 1칸부터 N칸까지의 경우를 구해보면

1칸 : 1개

2칸 : 3개

3칸 : 5개

4칸 : 11개

...

N칸 : (n - 1번째 칸의 경우의 수) + 2 * (n - 2번째 칸의 경우의 수) 가 됩니다.

---

코드

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

public class Main {
	public static int N;
	public static int[] memo = new int[1001];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		memo[0] = 1;
		memo[1] = 1;
		for (int i = 2; i <= N; ++i) {
			memo[i] = (memo[i - 1] % 10007) + ((2 * memo[i - 2]) % 10007); 
		}
		
		System.out.println(memo[N] % 10007);
	}
}

---

pyo7410/Algorithm