[백준_11727번] 2Xn 타일링 2

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

11727번: 2×n 타일링 2

[문제]

 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

 

[입력 조건]

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

[코드]

import java.util.*;

public class BaekJoon_11727 {
	static Integer[] dp;
	static int n;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		dp=new Integer[n+1];
		
		dp[0]=dp[1]=1;
		
		System.out.println(dynamic(n));
	}
	
	/*
	 * 동적 계획법
	 * n=1일 경우 1
	 * n=2일 경우 3
	 * n=3일 경우 5
	 * ...
	 * 
	 * 점화식은 dp[n] = (dp[n-2]*2) + dp[n-1]이 된다.
	 */
	public static int dynamic(int n) {
		if(dp[n]==null)
			dp[n]=(dynamic(n-1)+dynamic(n-2)*2)%10007;
		
		return dp[n];
	}
}

 

[고찰]

 이번 문제는 이전 11726과 거의 비슷한 문제로 규칙을 찾아 동적 계획법으로 풀어야 하는 문제였다. 그림을 그려가며 놓치는 경우의 수가 없다면 쉽게 해결할 수 있는 문제였다.