# How Many Fibs?/황재선

2006.1.4

## 접근 방법 ¶

반복적인 계산을 줄이기 위해서, bottom-up 방식으로 수열을 처음부터 계산하였다. 계산된 이전 값을 사용하여 다음 수열을 빠르게 얻을 수 있었다. Dynamic Programming을 처음으로 해보았다

## 소스 코드 ¶

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

public class Fibonacci {

return new Scanner(System.in).useDelimiter("\n").next().trim();
}

public int howManyFib(BigInteger start, BigInteger end) {
int howMany = 0;

BigInteger zero = new BigInteger("0");
BigInteger one = new BigInteger("1");
BigInteger two = new BigInteger("2");

if ((start.equals(zero) && end.equals(one)) ||
(start.equals(one) && end.equals(one)) ||
(start.equals(two) && end.equals(two))) {
return 1;
}
else if (start.equals(one) && end.equals(two)) {
return 2;
}
else if (start.equals(one)) {
howMany = 2;
}
else if (start.equals(two)) {
howMany = 1;
}

BigInteger[] fibRoom = new BigInteger[4];

fibRoom[1] = one;
fibRoom[2] = two;

while(true) {

if (start.compareTo(fibRoom[3]) <= 0 && fibRoom[3].compareTo(end) <= 0) {
howMany++;
}

if (fibRoom[3].compareTo(end) > 0) {
break;
}

fibRoom[1] = fibRoom[2];
fibRoom[2] = fibRoom[3];
}
return howMany;
}

public void printNumOfFibs(int numOfFibs) {
System.out.println(numOfFibs);
}

public static void main(String[] args) {
Fibonacci fib = new Fibonacci();

while(true) {
if (line.equals("0 0")) {
break;
}

BigInteger start = new BigInteger(line.split(" ")[0]);
BigInteger end = new BigInteger(line.split(" ")[1]);

int numOfFibs = fib.howManyFib(start, end);
fib.printNumOfFibs(numOfFibs);
}
}

}
```

## Test Code ¶

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

import junit.framework.TestCase;

public class TestFibonacci extends TestCase {
public void testSample() {
Fibonacci fib = new Fibonacci();

assertEquals(5, fib.howManyFib(new BigInteger("10"), new BigInteger("100")));
assertEquals(4, fib.howManyFib(new BigInteger("1234567890"),
new BigInteger("9876543210")));

assertEquals(1, fib.howManyFib(new BigInteger("1"), new BigInteger("1")));
assertEquals(1, fib.howManyFib(new BigInteger("0"), new BigInteger("1")));
}
}
```

----
HowManyFibs?