[알고리즘]프로그래머스 12945번 - 피보나치 수

프로그래머스 12945번 - 피보나치 수

프로그래머스 12945번 - https://programmers.co.kr/learn/courses/30/lessons/12945

 

요구사항

1. N번째 피보나치 수를 1234567로 나눈 나머지를 반환하라.

 

피보나치 수 점화식

F[N] = F[N-1] + F[N-2] ( N >= 2 )

F[0] = 0, F[1] = 1

 

요구사항 분석 및  풀이과정

1. 피보나치 점화식을 이용하여 N번째 피보나치 수까지 구하여 1234567로 나눈 나머지를 반환하여 준다.

 

(a + b) % k = ((a % k) + (b % k)) % k

 

피보나치 수가 얼마까지 커지는지 파악하기가 어려워서,

오버 플로우 방지를 위하여 마지막에 나눠주는 것이 아니라 매번 구할 때 나누어줬다.

 

소스코드 작성

class Solution {
    
    private final int MOD = 1234567;
    
    private long mod(long v1, long v2) {
        return ((v1 % MOD) + (v2 % MOD)) % MOD;
    }
    
    public int solution(int n) {
        long[] dp = new long[n+1];
        
        dp[0] = 0;
        dp[1] = 1;
        
        for(int i = 2; i <= n; i++) {
            dp[i] = mod(dp[i-1], dp[i-2]);
        }
        
        return (int)dp[n];
    }
}

 

결과

 

소스코드 깃허브 주소

링크