[백준_11726번] 2Xn 타일링

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

11726번: 2×n 타일링

[문제]

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

 

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_11726 {
	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일 경우 2
	 * n=3일 경우 3
	 * n=4일 경우 5
	 * ...
	 * 
	 * 점화식은 dp[n] = dp[n-2] + dp[n-1]이 된다.
	 */
	public static int dynamic(int n) {
		if(dp[n]==null) {
			dp[n]=(dynamic(n-2)+dynamic(n-1))%10007;
		}
		return dp[n];
	}
}

 

[고찰]

 이번 문제는 동적 계획법 문제였다. 이전에 풀어봤던 동적 계획법 문제와 비슷해 우선 규칙을 찾기 위해 n이 5일때까지 그림을 그려 경우의 수를 세보았다. 그랬더니 dp[n] = dp[n-2] + dp[n-1]이라는 규칙을 쉽게 찾을 수 있었다. 이 점화식을 동적 계획법을 사용하여 구현하는 것 또한 어렵지 않게 해결할 수 있었다.