10359 - Tiling

10359 - Tiling.java

/**
 * Tittle:	10359 - Tiling
 * Author:	Cheng-Shih, Wong
 * Date:	2015/07/08
 */

import java.util.*;
import java.math.*;

public class Main {
	
	public static void main( String[] args ) {
		int n;
		int N = 300;
		BigInteger[] dp = new BigInteger[N];
		dp[0] = BigInteger.ONE;
		for( int i=1; i < 300; ++i )
			dp[i] = BigInteger.ZERO;
		Scanner input = new Scanner( System.in );

		// init
		for( int i = 0; i<250; ++i ) {
			dp[i+1] = dp[i+1].add( dp[i] );
			dp[i+2] = dp[i+2].add( dp[i].add(dp[i]) );
		}

		// input
		while( input.hasNext() ) {
			n = input.nextInt();

			// output
			System.out.println( dp[n] );
		}
	}
}