[ 문제 설명 ]
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를 들어
- F(2) = F(0) + F(1) = 0 + 1 = 1
- F(3) = F(1) + F(2) = 1 + 1 = 2
- F(4) = F(2) + F(3) = 1 + 2 = 3
- F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
[ 제한 사항 ]
* n은 1이상, 100000이하인 자연수입니다.
[ 입출력 예 ]
n | return |
3 | 2 |
5 | 5 |
class Solution {
public int solution (int n) {
if (n == 0 || n == 1)
return n;
int[] bottomUp = new int[n + 1];
bottomUp[0] = 0;
bottomUp[1] = 1;
for (int i = 2; i < n + 1; i++)
bottomUp[i] = bottomUp[i - 1] % 1234567 + bottomUp[i - 2] % 1234567;
return bottomUp[n] % 1234567;
}
}
피보나치 수열을 구하는 가장 흔한 방법은 재귀함수를 이용하는 것입니다.
하지만 재귀함수를 사용하게 되면 똑같은 계산을 반복적으로 수행해야 함으로 런타임 에러가 발생하게 됩니다.
따라서 피사노 주기를 이용해야 합니다.
"피사노 주기"란, 피보나치 수열의 항들을 m으로 나눈 나머지가 주기(period)를 가지고 반복되는 것을 일컫습니다.
피사노 주기를 이용해서 문제를 풀기 위해 배열을 할당해 문제를 풀었습니다.
결과값을 1234567로 나눈 나머지 값과 각각의 수를 1234567로 나눈 나머지 값들을 더하는 것의 결과값은 같으므로
오버플로우를 고려하여 미리 1234567로 나누어 나머지 값들을 구했습니다.