[Algorithm] Programmers :: 피보나치 수

https://programmers.co.kr/learn/courses/30/lessons/12945?language=cpp 

코딩테스트 연습 - 피보나치 수

 

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

이 문제는 피보나치를 구현하는것보다는 1234567로 나눈 값을 리턴한다는게 좀 더 포인트같다.

피보나치는 워낙 유명해서... 재귀로 하면 조금만해도 시간초과기 때문에 DP로 푼다는거는 알고있었다.

근데 나는 처음에 최종결과 fa[n]에 1234567을 나눈 나머지를 리턴했다가 틀렸다고 떠서 뭔가 했다.

생각해보니 수가 기하급수적으로 커지기 때문에 바로바로 1234567로 나눈 나머지값을 넣어놔야 값이 안터진다.