[백준] 2xn 타일링 2 11727 - JAVA

문제

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

11727번: 2×n 타일링 2

풀이

DP 문제다. 

2x3 경우를 생각해보자

n은 열의 개수를 나타내고 dp[n] 은 2xn일때 만들 수 있는 경우의 수를 나타낸다.

노란색 : 3번째 칸을 2x1로 놓았을 경우 dp[2]이 그대로 dp[3]이 된다.

파란색 : 3번째 칸을 2x1로 놓지 않았을 경우 2x2 혹은 1x2를 사용할 수 있다. 이는 dp[1]과 2가 곱해져야 한다.

 

따라서 dp식은 다음과 같다.

dp[3] = dp[i-1] + dp[i-2] * 2

 

코드

import java.util.*;
import java.io.*;

public class Main {
			
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		int n = Integer.parseInt(br.readLine());

		long arr[] = new long[1002];
		
		arr[1] = 1;
		arr[2] = 3;
		
		for(int i=3;i<=n;i++) {
			long sum = arr[i-1];
			sum += arr[i-2] * 2;
			
			arr[i] = sum%10007;
		}
		
		System.out.println(arr[n]);
		
	}
	
	   
}