[Algorithms] 백준 11726 2XN 타일링

Dynamic programming 사용

n =1일때 방법 1개

n =2일때 방법 2개

n =3일때 방법 3개

n =4일때 방법 5개

n =5일때 방법 8개

n =6일때 방법 13개

이처럼  dp[n] = dp[n-2]+ dp[n-1] 이다. 

 

이를 활용해서 문제 해결

 

package boj;

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

public class boj_11726_2xn타일링 {
	private static int N;
	private static int[] dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		dp = new int [N+1];
		dp[0] = 1;
		dp[1] = 1;
		bottomUp(N);
		
		
	}

	private static void bottomUp(int n) {
		for(int i=2 ;i<=n; i++) {
			dp[i] = dp[i-2]+ dp [i-1];
			dp[i] %= 10007; 
		}
		
		System.out.println(dp[n]);
	}
}