프로그래머스 피보나치 수

n번째의 피보나치 수를 구한 뒤 1234567로 나눈 나머지를 출력

풀이과정

먼저 n+1크기의 배열을 만들고
for문을 이용해 arr[n-1] + arr[n-2]를 해준다음
마지막에 arr[n]%1234567을 해주었다
근데 안돼

그래서 그 다음에는 재귀를 이용한 방법으로했다
재귀를 이용하면 이진트리 느낌으로 피보나치 함수가 재귀적으로 동작하고 나중에는 다시 끝에서 리턴되어서 합쳐지는 구조이다
근데 이걸 사용하니 시간초과가 뜬다.. 왜냐하면 100000번째 피보나치까지 구해야되기 때문이다

그래서 다시 for문과 배열을 이용해서 푸는데 계속 7번 케이스부터 실패가 떠서 어디가 문제지 하고 찾아본결과 역시나 오버플로우 문제였다.

오버플로우를 줄이기위해 long을 써보았지만 그래도 오버플로우가 발생한다
이거 무슨 long보다 길어..

하지만 방법이 남아있었다 바로 1234567나머지 이거를 이용하면 1234567의 나머지를 배열에 넣기때문에 오버플로우가 발생하지 않는다

그래서 for문 중간에 %1234567을 해주었다

코드

class Solution {
    public int solution(int n) {
        long[] arr = new long[n+1];
        arr[0] = 0;
        arr[1] = 1;
        
        for(int i=2; i<=n; i++) {
            arr[i] = (arr[i-1]+arr[i-2])%1234567;
        }
        int answer = (int)arr[n];
        return answer;
    }
}

참 간단한 코드다
n은 2부터 시작하기때문에 미리 0과 1번째에 값을 주었고
매번 for문이 돌때마다 1234567의 나머지를 구하게 만들었다
그리고 마지막에 제일 끝에 배열의 값을 answer에 넣어주면 된다