[BOJ] 백준 10826번 : 피보나치 수 4 (JAVA)

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

 

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일 때까지 피보나치 수를 써보면 다음과 같다.

 

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

 

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

 

 

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

 

 

풀이

큰 수 연산과 관련된 문제였습니다.

 

n번째 피보나치 수를 구하라는 문제인데, n이 최대 10,000 이라서 long 자료형으로도 커버가 불가능했습니다.

우리는 보통 long 자료형보다 더 큰 자료형을 모르는 경우가 많은데, 놀랍게도 '무한대'를 커버할 수 있는 자료형이 있습니다.

 

바로 BigInteger 라는 자료형을 이용하는 것입니다.

이것에 대한 사용법은 아래 블로그에서 잘 나와있습니다.

 

 

[JAVA] 무한대 정수 BigInteger 사용하기

 

 

위 BigInteger를 사용하여 우리가 흔히 알던 피보나치 관련 다이나믹 프로그래밍 코드를 짜시면 됩니다.

Bottom-up 방식을 통해서 dp[i] = dp[i - 2] + dp[i - 1] 점화식으로 dp 배열을 쭉 저장해 나가고, 마지막에 dp[N]을 출력하면 끝입니다.

 

 

아래는 위 내용을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.