프로그래머스 - 피보나치 수

프로그래머스 - 피보나치 수

그냥 풀었다가 시간초과 맞았다.

int fibo(int n) {
    if(n == 0)
        return 0;
    if(n == 1 || n == 2)
        return 1;
    return fibo(n - 1) + fibo(n - 2);
}

위와 같이 피보나치 함수를 만들어서 재귀로 풀면 7번부터 시간초과 난다.

#include <string>
#include <vector>

using namespace std;

int map[100001] = { 0, 1 };
int solution(int n) {
    int answer = 0;
    
    for(int i=2;i<100001;i++) 
        map[i] = (map[i - 1] + map[i - 2]) % 1234567;
    
    answer = map[n];
    
    return answer;
}

따라서 위와 같이 미리 map을 다 만들어 놓고 바로 답을 리턴해줘야 한다.

1234567을 미리 모듈러 연산을 해주도록 했다.

• (a + b) % n = (a % n) + (b % n)
• (a + b) % n = (a + b % n) % n

위 두식을 만족하기 때문에 피보나치 수열을 구할 때, 각 단계마다 바로바로 모듈러 연산을 적용해줘도 된다.

• 모듈러 연산을 안한 피보나치 수열
  1 1 2 3 5 8 13 21 34 ...
• 10으로 모듈러 연산을 적용한 피보나치 수열
  1 1 2 3 5 8 3 1 4 ...