[백준 온라인 저지(BOJ)] 10826번 피보나치 수 4 자바(java) 풀이 ( BigInteger 이용)

안녕하세요 호호만두에요

이번에는 백준 온라인 저지(BOJ)의 10826번 피보나치 수4를 자바로 풀어봅시다

https://www.acmicpc.net/problem/10826

10826번: 피보나치 수 4

 

이 문제의 n이 최대 10000이라는 것에 주의해야되요

작아 보이는 수 같지만 피보나치 수를 구하면 저어어어엉말 커져요

출력해보니까 대충 2000자리가 넘어요

그래서 long 형으로 구하게 되면 overflow나서 이상한 수가 출력되요

(참고로 64bit long형 max 값은9223372036854775807대 충 920경....

그래서 자바에서는 BigInteger를 이용하여 간단하게 풀 수 있습니다

이는 java.math.BigInteger 를 import해서 사용하실 수 있습니다

 

1. n을 입력받는다

2. BigInteger 배열을 초기화 한다(i번째 idx : i번째 피보나치 수)

3. for문을 순회하며 이 전 두수를 더해주면서 다음 피보나치 수를 구해나가며 배열에 저장

코드는 아래를 참고해주세요!!

	import java.io.BufferedReader;
	import java.io.BufferedWriter;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.io.OutputStreamWriter;
	import java.math.BigInteger;
	class Main{
	static BigInteger arr[];
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	int n = Integer.parseInt(br.readLine());
	arr = new BigInteger[n+2];
	arr[0] = BigInteger.ZERO;
	arr[1] = BigInteger.ONE;
	for(int i=2; i<=n; i++) {
	arr[i] = arr[i-2].add(arr[i-1]);
	}
	bw.write(String.valueOf(arr[n]));
	bw.flush();
	br.close();
	bw.close();
	}
	}

view raw 10826_fibonacci4.java hosted with ❤ by GitHub