피보나치 수

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

 

n번째 피보나치 수를 1234567로 나눈 나머지를 구하는 문제다.

 

피보나치 수를 구하는 방법엔 여러 방법이 있겠지만 배열을 사용했다.

 

n의 범위를 고려하지 않고 처음엔 int형을 사용했다.

public int useInt(int n) {
    int[] fib = new int[n+1];
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i <= n; i++) {
        fib[i] = (fib[i - 1] + fib[i-2]);
    }

    return fib[n]%1234567;
}

 

테스트7부터 테스트 케이스를 통과하지 못한다.

Long으로 바꾸면 될까 했지만 n의 범위가 워낙 큰 탓에 될리는 없고,

 

int[]를 사용하면서, 배열에는 피보나치 수가 아닌 피보나치 수를 1234567로 나눈 나머지를 저장하는 방식으로 수정했다.

(대충 생각해보면 (a % c) + (b % c) = (a + b) % c)

public int useInt(int n) {
    int[] fib = new int[n+1];
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i <= n; i++) {
        fib[i] = (fib[i - 1] + fib[i-2])%1234567;
    }

    return fib[n];
}