mingssssss

1. 문제

2. 코드

import java.util.*;

class Solution { 

    static long[] memo;
    static long answer;

    public long solution(int n) {

        memo = new long[1000000];
        answer = 0;

        answer = fibo(n);

        return Long.valueOf(answer % 1234567);
    }

     private static long fibo(int n) {

        if (n <= 1) {
            return n;

        } else if (memo[n] != 0) {
            return memo[n];
        } else {
            return memo[n]  = (fibo(n - 1) % 1234567) + (fibo(n - 2) % 1234567);
        }
    }
}

3. 리뷰

프로그래머스 스킬체크 난이도 2문제이다.

아~주 익숙하고 간단한 피보나치 수열 문제이다.

하지만 예상했듯이 기본적인 재귀 함수로 풀면 시간초과가 난다.

long형으로 변환하고 ArrayList도 써봤지만, 문제에서 요구하는 풀이법이 아니다.

고민하던 중 좋은 글이 있어서 첨부한다.

44번째 피보나치수 부터 이미 int형의 범위가 넘어가므로, 다른 방식의 풀이법을 써야 한다.

문제에서 요구하는 1234567로 나눠야 하는 이유가 여기에 있다.

(A + B) % C = ((A % C) + (B % C)) % C는 사칙연산에서 배운 기본적인 내용이다.

이 원리를 이용하면, 매번 피보나치 수열을 구한 뒤에 1234567을 나눈 결과와,

N번째 피보나치 수열을 1234567로 나눈 결과와 동일하게 된다.

이 글을 보자마자 한 대 맞은 것 거처럼 감탄했다...

알고리즘 문제에 수학적 기법을 적용하는 것이 중요하다고 생각했다.