[Level 2] 9. 피보나치 수

9. 피보나치 수

Algorithm - Level 2

- 풀이

1. 피보나치 수도 이전의 수에 영향을 받는다.

-> Dynamic programming 점화식 이용.

2. int형의 범위를 초과할 수 있다. && 2 이상의 수가 입력되면 1234567로 나눈 나머지를 구한다.

-> modular 연산은 수들을 다 더한 후 나머지를 구하나, 먼저 나머지를 구한 후 덧셈한 것이 결과가 같다.

#include <string>
#include <vector>
 
using namespace std;
 
int solution(int n) {
    int answer = 0;
    int dp[n+1];
    
    if(n==1)
        return 1;
    
    dp[0] = 0;
    dp[1] = 1;
 
    for(int i=2; i<n+1; i++){
        dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
    }
 
    answer = dp[n];
    
    return answer;
}