2006.1.8

== 쓰레드 ==
 * 동적 프로그래밍 기법을 사용.
 * BigInteger 매우 강력하다!

== 소스 코드 ==
{{{~java
import java.math.BigInteger;
import java.util.Scanner;

public class Counting {

	public String readLine() {
		try {
			return new Scanner(System.in).useDelimiter("\n").next().trim();	
		}
		catch (Exception e) {
			return null;
		}		
	}
	
	public BigInteger count(int n) {
		BigInteger zero = new BigInteger("0");
		BigInteger one = new BigInteger("1");
		BigInteger two = new BigInteger("2");

		BigInteger[] sum = new BigInteger[n + 1];
		sum[0] = zero;
		sum[1] = two;
		
		for(int input = 2; input <= n; input++) {
			BigInteger numOfEachCounting = zero;
			for(int i = 1; i <= 3 && i <= input; i++) {
				BigInteger first = zero;
				if (i > 1 && input - i == 0) {
					first = one;
				}
				
				BigInteger second = i == 1 ? 
								two.multiply(sum[input - i]) : sum[input - i];
				
				numOfEachCounting = numOfEachCounting.add(first.add(second));
			}
			sum[input] = numOfEachCounting;
		}
		return sum[n];
	}
	
	public void printCount(BigInteger number) {
		System.out.println(number);
	}
	
	public static void main(String[] args) {
		Counting c = new Counting();		
		while(true) {
			String line = c.readLine();
			if (line == null || line.equals("")) {
				break;
			}
			int n = Integer.parseInt(line);
			BigInteger number = c.count(n);
			c.printCount(number);
		}
	}
}
}}}

{{{~java
import java.math.BigInteger;

import junit.framework.TestCase;

public class TestCounting extends TestCase {
	
	public void testOne() {
		Counting c = new Counting();
		assertEquals(new BigInteger("2"), c.count(1));
	}
	
	public void testTwo() {
		Counting c = new Counting();
		assertEquals(new BigInteger("5"), c.count(2));
	}
	
	public void testThree() {
		Counting c = new Counting();
		assertEquals(new BigInteger("13"), c.count(3));
	}

	public void testFour() {
		Counting c = new Counting();
		assertEquals(new BigInteger("33"), c.count(4));
	}
	
	public void testFive() {
		Counting c = new Counting();
		assertEquals(new BigInteger("84"), c.count(5));
	}
	
	public void testMax() {
		Counting c = new Counting();
		String output = "7804866167757385351726298167749579946964405850225254539132682472794981869745040537197592219996231328486687877730240352396489040560067523395940725030942516170568234738182127635234624655775531244438437118253542255365923486221253172456203933189283985689116139597563337647696143005496252287734941893682019406515104829885420261968884040123236083676226862353415881286645117793584639279853095668990201156175586714";
		assertEquals(new BigInteger(output), c.count(1000));
	}
}
}}}

----
[Counting]