[프로그래머스] 피보나치 수

프로그래머스의 Lv.2 피보나치 수 문제 풀이

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

문제 풀이
피보나치 수열에 대해서 생각을 해보면 n이 0, 1일때는 그냥 그 값이 바로 나온다. 그래서 n이 2이상이어야 한다. 그것을 생각하고, a, b를 0, 1로 초기화하고 for문을 사용하여 순회를 한다. 순회를 하면서 처음에는mod로 나누어 주지않아 오버플로우가 발생했었다. 오버플로우를 방지하기위해 나머지를 출력하고, a, b의 값을 갱신하여 최종 값 b를 반환하였다.

코드

public int solution(int n) {
   int answer = 0;
   int a = 0;
   int b = 1;
   int mod = 1234567;
   
   if (n <= 1) {
     return n;
   }
   for (int i = 2; i <= n; i++) {
     answer = (a + b) % mod;
     a = b;
     b = answer;
   }
   return b;
 }