피보나치 수

들어가는 말

피보나치 수열을 구하는 문제다. 처음에는 재귀로 풀려 했는데, 피보나치는 재귀로 풀면 시간이 오래 걸린다는 교수님의 말씀을 떠올리고 반복문으로 풀었다. 다만, 문제는 1234567로 나눠야 한다는 사실...

코드 설명

처음에는 배웠던 대로 tmp, current, last변수를 두고 반복문을 이용해서 풀었다. 그런데 자꾸만 틀렸다고 하는 거 아닌가. 결과 값을 1234567로 나눠도 자꾸만 틀렸댄다. 그래서 인터넷을 찾아보니까 배열로 푼 사람이 있어서 배열로 풀었더니 통과했다. 하지만, 배열로 풀어서 통과한 게 아니었다. 결과값을 계산하면 바로바로 1234567로 나눠야 하는데, 나는 결과값만 1234567로 나눠서 틀렸던 것이다! 그러므로 내가 처음 풀었던 방법이 아예 틀렸다는 것 아니라는 점.

코드

제출 코드

#include <string>
#include <vector>
using namespace std;

int arr[100010];

int solution(int n) {

    arr[0] = 0;
    arr[1] = 1;

    for(int i=2; i<=n; i++){

        arr[i] = arr[i-2] + arr[i-1];
        arr[i] = arr[i] % 1234567;
    }

    return arr[n];
}

제출 후 변경한 코드

#include <string>
#include <vector>
using namespace std;

int solution(int n) {
    
    int tmp, current = 1, last = 0;
    
    for(int i=2; i<=n; i++){
        tmp = current;
        current = current + last;
        current = current % 1234567;
        last = tmp;
    }
    
    return current;
}