# Counting/황재선

2006.1.8

## 쓰레드 ¶

• 동적 프로그래밍 기법을 사용.
• BigInteger 매우 강력하다!

## 소스 코드 ¶

```~java
import java.math.BigInteger;
import java.util.Scanner;

public class Counting {

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];

}
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) {
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