다이나믹 프로그래밍_11726 번 : 2xn 타일 JAVA

 

다이내믹 프로그래밍 Bottom-up 방식으로 풀어낼 수 있다.

문제를 푸는 순서는 다음과 같이 진행된다.

 

1. 테이블 정의

2. 점화식 찾기

3. 초기값 찾기

 

테이블 정의

D[i] 2 X i 전체 타일을 2x1 타일 이나 2x2 타일로 채우는 방법의 수

 

점화식 찾기

D[i] = D[i-2] + D[i-1];

D[i]는 D[i-2] 방법의 수에서 추가로  2x2 타일을 채우면 되고, D[i-1]에서 2x1 타일을 채우면 된다. 둘이 합친 방법의 수가 D[i] 값이다.

 

초기값 찾기

D[1] = 1

D[2] = 2

 

import java.io.*;

public class Main{
	public static void main(String[] args){
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(tillingMethod(N));
    }
    public static int tillingMethod(int N){
    	int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 2;
        
        if(N<2)
        	return dp[N];
        for(int i=3;i<=N;i++){
        	dp[i] = (dp[i-2] + dp[i-1]) % 10007;
        }
        return dp[N];
    }
}