Lv.2 : 피보나치 수

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• n번째 피보나치수를 1234567로 나눈 나머지를 리턴한다.

🔸 문제 풀이 🔸

• 피보나치수가 커져갈때마다 1234567로 나눠서 누적한다.

---

🔸 코드 🔸

class Solution {
    public int solution(int n) {        
        int a = 0;
        int b = 1;
        int c;
        
        for(int i = 2; i <= n; i++) {
            c = (a + b) % 1234567;
            a = b;
            b = c;
        }
        
        return b;
    }
}

🔸 코드 해석 🔸

• n의 입력은 2~n 이므로 0번째와 1번째 피보나치수는 초기화해서 사용한다.
• a+b를 1234567로 나눠서 누적해도, 최종 n번째 피보나치수를 1234567로 나눈 나머지와 같다.
  • 최종 값을 나머지 처리한 것과 나머지들을 누적한 것이 같다는 원리

---

🔸 end 🔸

• 피보나치수라는 흔한 주제만큼 크게 어려울게 없던 문제이다.
• 다른 풀이로는 재귀로 피보나치를 구현하거나 배열에 저장하는 방식도 있었지만 메모리가 비효율적이었다.