백준 11726, 2 x n 타일링

문제

문제요약

1. 2*n 크기의 직사각형이 존재할때 1*2 타일과 2*1 타일로 채우는 경우의 수를 구합니다.
2. 1<=n<=1000
3. 출력시 채우는 경우의 수를 10007로 나눈 나머지를 출력합니다.

문제풀이

n=1~4의 패턴으로 봤을때 2*n 타일링의 경우의 수는 피보나치 수열을 따르고 있습니다. 따라서 점화식을 구성하면 다음과 같습니다.

소스코드

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

public class Main {
	static long[] arr = new long[1001];
	public static long solution(int n)
	{
		if(n<=2)
		{
			arr[n] = n;
			return arr[n];
		}

		long first = (arr[n-1]!=0 ? arr[n-1] : solution(n-1));
		long second = (arr[n-2]!=0 ? arr[n-2] : solution(n-2));
		
		arr[n] = first + second;
		return arr[n]%10007;
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		System.out.println(solution(n));
		
	}
}