피보나치 수의 개수 (BOJ 6571)
1. 문제에 대한 이해
- 우리가 풀어야 할 문제는 무엇인가?
- 주어진 자료는 무엇인가?
- 조건은 무엇인가?
- 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
- 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라.
- 우리가 풀어야 할 문제는 무엇인가?
-> 두 수 a와 b가 주어졌을 때,
구간 [a,b]에 포함되는 피보나치 수의 개수를 구하는 프로그램을 작성하시오
- 조건은 무엇인가?
-> 입력은 여러 개의 테스트 케이스로 이루어져 있다
-> 각 테스트 케이스는 음이 아닌 두 정수 a와 b로 이루어져 있다.
-> 입력의 마지막 줄에는 0이 두개 주어진다.
2. 계획
- 전에 비슷한 문제를 알고 있는가?
- 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
- 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
- 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
- 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
- 자료는 모두 사용했는가?
- 조건을 모두 사용했는가?
- 문제에 포함된 핵심적인 개념은 모두 고려했는가?
- 전에 비슷한 문제를 알고 있는가?
-> 피보나치 문제를 풀어봤다
- 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
-> 피보나치 수열. 그리고
1 2 3 4 5 6 7 8 9
1 2 3 5 8 13 21 34 55
1 100
- 어떻게 문제를 풀 것인가?
-> 피보나치 수열을 돈다
-> 어떤 수가 되었을 때,
-> 그 수가 a보다 크고 b보다 작은지 판단한다
-> 만약 그러하다면 개수를 + 한다
-> a보다 작다면 계속해서 간다
-> b보다 크다면 거기서 멈춘다.
- 수가 매우 큰 수이다
-> 즉, BigInteger를 사용해야 한다
-> BigInteger를 어떻게 사용하는가?
- arr에 담아 놓았다.
-> 새로 만든다
-> 그것에 대해 검사한다
-> 검사하고 카운트한다
-> 카운트하고 arr에 넣는다.
3. 실행
- 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.
import java.util.*;
import java.math.*;
public class Main {
public long fibonacci(BigInteger a, BigInteger b){
long cnt = 0;
ArrayList<BigInteger> arr = new ArrayList<BigInteger>();
arr.add(new BigInteger("1"));
arr.add(new BigInteger("2"));
if(a.compareTo(arr.get(0)) <= 0 && (arr.get(0)).compareTo(b) <= 0){
cnt++;
}
if(a.compareTo(arr.get(1)) <= 0 && (arr.get(1)).compareTo(b) <= 0){
cnt++;
}
while(true){
int len = arr.size();
BigInteger tmp = arr.get(len-2).add(arr.get(len-1));
if( a.compareTo(tmp) <= 0 && tmp.compareTo(b) <= 0){
cnt++;
}
if(b.compareTo(tmp) == -1){
break;
}
arr.add(tmp);
}
return cnt;
}
public static void main(String args[]) {
Main c = new Main();
Scanner sc = new Scanner(System.in);
while(true){
StringTokenizer st=new StringTokenizer(sc.nextLine());
BigInteger a = new BigInteger(st.nextToken());
BigInteger b = new BigInteger(st.nextToken());
if(a.compareTo(new BigInteger("0"))==0&&b.compareTo(new BigInteger("0"))==0) break;
long result = c.fibonacci(a, b);
System.out.println(result);
}
}
}4. 반성
- 문제를 다른 방식으로 해결할 수 있는가?
- 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
- 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?
- 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?
-> BigInteger 활용법에 대해서 배웠다.
-> BigInteger를 입력 받을 때는, StringTokenizer를 활용할 수 있고,
-> StringTokenizer란 무엇인가?
-> StringTokenizer (Java Platform SE 7 ) (oracle.com)
- BigInteger를 새로 선언할 때는, new BigInteger("")로 선언할 수 있다.
또한 BigInteger끼리 더할 때는 A.add(B)와 같이 더할 수 있다.
- 또한 BigInteger끼리 compareTo로 비교할 수 있다.
a,compareTo(b)== -1이라는 것은 a가 b보다 작다는 것이다
a.compareTo(b)== 0이라는 것은 a와 b가 같다는 것이다.
a.compareTo(b) > 1이라는 것은 a가 b보다 크다는 것이다.