피보나치 수 (level2)
피보나치 수는 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이하인 자연수입니다.
풀이
재귀로만 풀면 시간초과가 나기 때문에 메모이제이션을 활용했다.
불필요한 계산을 줄이기 위해 피보나치 수가 계산된 수는 배열에 저장을 한다.
1과 0일 때는 각각 1과 0을 리턴해준다.
만약 현재 숫자가 배열에서 0이아닌 계산된 값이 들어갔다면 그 값을 리턴해준다.
문제에서 잘 나와있지 않지만 값을 계산할 때 1234567로 나눈 나머지로 저장을 해야한다.
코드
class Solution {
public int solution(int n) {
arr = new int[100001];
int answer = fibonacci(n) % 1234567;
return answer;
}
static int arr[];
public static int fibonacci(int n) {
if (n == 1) {
return 1;
}else if( n == 0) {
return 0;
}
else if( arr[n] != 0) {
return arr[n];
}else {
arr[n] = fibonacci(n-1)% 1234567 + fibonacci(n-2)% 1234567;
return arr[n];
}
}
}