[프로그래머스] 12945번 - 피보나치 수 (JAVA)

출처: 프로그래머스 코딩테스트 연습

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

프로그래머스

---

문제

 

풀이

이 문제는 1) n번째 피보나치 수를 구하는 방법과 2) 1234567로 나눈 나머지(모듈러 연산)가 포인트 입니다.

 

1. DP로 n번째 피보나치 수 구하기

피보나치 수는 문제 설명처럼 F(n) = F(n-1) + F(n-2) 가 적용되는 수입니다. 다시 말해 현재의 전 번째 수와 전전 번째 수를 합한 값이 현재의 값이 되는 것입니다. 피보나치 수를 구하는 방법은 재귀함수 등이 있지만 저는 효율성을 위해 DP를 활용하여 풀었습니다.

 

DP 테이블에는 i번째 피보나치 수가 들어가게 됩니다.

그렇다면 점화식은 dp[i] = dp[i-1] + dp[i-2] 로 쓸 수 있게 됩니다. 이 때 dp[0] = 0, dp[1] = 1이 됩니다.

따라서 2번째 피보나치 수부터 n까지 차례대로 dp 값을 구하면 n번째 피보나치 수를 구할 수 있게 됩니다.

dp[0] = 0;
dp[1] = 1;

for(int i=2; i<n+1; i++){
	dp[i] = dp[i-1] + dp[i-2];
}

 

2. 1234567로 나눈 나머지

다음으로는 1234567로 나눈 나머지를 구해야 합니다. 

dp 값을 위 방식대로 구한 다음 return dp[n] % 1234567 하게 되면 문제에서 테스트케이스 7 - 14번을 실패하게 됩니다.

 

이는 n의 값이 너무 커지게 되면 피보나치 수 값이 int 형이 나타낼 수 있는 값의 범위를 넘어가기 때문에 오버플로우가 생기는 때문입니다.

int에서 long형으로 바꿔주게 되더라도 n의 최댓값인 100,000인 경우에는 범위를 넘어 오버플로우가 생깁니다.

 

이때 활용할 수 있는 개념이 모듈러 연산의 성질입니다.

모듈러 연산의 덧셈 성질로 인해 (A+B) mod C = (A mod C + B mod C) mod C 가 성립합니다.

(dp[i-1] + dp[i-2]) mod 1234567는 (dp[i-1] mod 1234567 + dp[i-2] mod 1234567) mod 1234567와 같습니다.

따라서 i번째 피보나치 수에 모듈러 연산을 한 값과, 모듈러 연산을 한 나머지 값으로 i번째 피보나치 수를 구한 값이 같습니다. 

 

예를 들어, 44번째 피보나치 수는 433494437입니다. 이를 1234567로 나눈 나머지 값은 161420입니다.

44번째 피보나치 수는 43번째와 42번째 피보나치 수를 더한 값이므로 이를 모듈러 연산 식으로 쓰면 다음과 같습니다.

 

(dp[43] + dp[42]) mod 1234567

= (dp[43] mod 1234567 + dp[42] mod 1234567) mod 1234567

= (267914296 mod 1234567 + 165580141 mod 1234567) mod 1234567

= (13257 + 148163) mod 1234567

= 161420

 

으로 44번째 피보나치 수를 구하고 나머지를 구한 값과, 나머지 값을 가지고 44번째 피보나치 수를 구한 값이 같은 것을 확인할 수 있습니다.

 

따라서 dp 테이블에는 1234567로 나눈 나머지 값이 들어가게 되고, dp 점화식은 dp[i] = (dp[i-1] + dp[i-2]) % 1234567이 됩니다.

 

 

소스코드

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

 

 

---

이 포스팅은 단지 취준생의 입장에서 공부하며 작성된 글입니다! 잘못된 부분이 있다면 언제든지 알려주세요! 공부에 많은 도움이 됩니다. 감사합니다🙇‍♀️