2×n 타일링 2 (Silver III)

문제 링크

문제 설명

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

문제 풀이

• 2*n 타일링 문제에서 그냥 피보나치 구나 ! 하고 넘어갔으면 이 문제에서 또 바로 걸렸을 텐데 그 때 고민한 보람이 있었다
• dp[n]번째 올 수 있는 경우의 수는
• | 얘가 맨 앞에 오는 경우 그래서 나머지는 구해진 최선의 경우의 수 dp[n-1]
• = 얘가 맨 앞에 오는 경우 dp[n-2]
• ㅁ 얘가 맨 앞에 오는 경우 dp[n-2]
  => 따라서 dp[n] = dp[n-1] + dp[n-2] * 2

디피 문제는 풀 땐 너무 어렵고 생각하기가 힘든데 풀고 나면 세상 간단하다,, 점화식을 생각해내기가 힘들어서 그런 것 같다 ㅠ

Solution

import java.util.Scanner;

// 2*n 타일링 2
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] dp = new int[10001];
		dp[1] = 1; // 2*1 일때
		dp[2] = 3; // 2*2 일때

		System.out.println(tile(dp, n) % 10007);
	}

	public static int tile(int[] dp, int n) {
		if (dp[n] != 0) {
			return dp[n];
		} else {
			// | 와 = 와 ㅁ 이 앞에 온 경우로 나눠서 생각할 수 있다
			// | 가 앞에 온 경우 n-1의 경우의 수
			// = 가 앞에 온 경우 n-2의 경우의 수
			// ㅁ 이 앞에 온 경우 n-2의 경우의 수
			dp[n] = tile(dp, n - 1) % 10007 + tile(dp, n - 2) % 10007 + tile(dp, n - 2) % 10007;
			return dp[n];
		}
	}
}