2×n 타일링 (Silver III)

문제 링크

문제 설명

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

문제 풀이

• 아이패드로 아무리 네모네모 그려가면서 해도 모르겠어서 구선생님 찬스를 빌렸더니 피보나치 수열,,이라네?
• 왜 피보나치 수열인가,, 진짜 이건 안보려고 한참을 또 고민했다
• 1,2,3,5,8,13 커지는 건 알겠어,, 그래서 왜?
• 그래서 한참을 본 결과 !
• 2*n 번째 에서 올 수 있는 타일의 경우의 수에서 생각 할 수 있는 건
• 맨 앞에 | 이놈 일자로 긴 놈이 와서 그 뒤로 저놈을 뺀 n-1개가 올 수 있는 경우의 수는 앞서 구해진 최선의 값 dp[n-1]와 같음
• 맨 앞에 = 이놈 두줄로 누운 놈이 와서 그 뒤로 n-2개는 앞서 구해진 최선의 값 dp[n-2]와 같음
  => 따라서 dp[n] = dp[n-1] + dp[n-2] 가 되므로 피보나치 수열이랑 같다
  가 결론이 되는 것이었다 !!!!

Solution

import java.util.Scanner;

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

		System.out.println(fibo(f, n) % 10007);
	}

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