프로그래머스 12945 - 피보나치 수 (Lv.2)

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

// 프로그래머스 12945 - 피보나치 수 (Lv.2)
// https://school.programmers.co.kr/learn/courses/30/lessons/12945

// 문제 설명
// F(0)=0, F(1)=1, n>=1에 대해 F(n)=F(n-1)+F(n-2).
// n번째 피보나치 수를 1234567로 나눈 나머지를 반환하라.

// 제약 조건
// 2 <= n <= 100,000

// 접근 — 반복 + 나머지 누적 O(n)
// 1) 재귀(F(n)=F(n-1)+F(n-2))는 같은 항을 지수적으로 중복 계산 → n=10만에서 사망
// 2) 0번째부터 위로 올라가며 직전 두 값(a, b)만 굴리면 O(n)·O(1)
// 3) 합이 커지므로 매 단계 % 1234567 — 나머지의 합도 나머지라 결과 불변, 오버플로도 차단

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int a = 0, b = 1;               // F(0), F(1)

    // F(2)부터 차례로 올라가며 두 값만 굴린다
    for (int i = 2; i <= n; i++) {
        int c = (a + b) % 1234567;  // 매 단계 나머지를 취해 오버플로·값 폭발 방지
        a = b;
        b = c;
    }

    return b;                        // 루프 종료 시 b == F(n) % 1234567
}

정리

• 피보나치는 정의가 곧 재귀식이라 solution(n-1)+solution(n-2)로 짜고 싶어지지만, 그러면 같은 부분 문제를 지수적으로 반복 계산해서 n이 조금만 커져도 못 끝낸다(O(2^n)). n이 최대 10만이므로 아래에서 위로 쌓아 올리는 반복문이 정답이다.
• 굳이 배열로 F(0)..F(n)을 전부 저장할 필요가 없다. F(n)을 구하는 데 필요한 건 직전 두 항뿐이라 변수 a, b 두 개만 굴리면 메모리 O(1)이다. c = a+b → a=b; b=c 한 칸씩 밀어내는 게 전부.
• 핵심 함정은 나머지를 마지막에 한 번이 아니라 매 단계마다 취하는 것이다. 모듈러 연산은 덧셈에 분배되므로 (a+b) % M을 매번 해도 결과는 똑같고, 대신 두 값이 항상 1234567 미만으로 유지된다. 그래서 a+b가 int 범위를 넘을 일이 없어 long long도 필요 없다.
• 반복 시작값에 주의. a=F(0)=0, b=F(1)=1로 두고 i=2부터 돌리면, 루프가 끝났을 때 b가 정확히 F(n)이 된다. 제약이 n>=2라 루프는 최소 1회는 돈다.
• 검증: 예제 n=3 → 2, n=5 → 5 통과. 추가로 n=2 → 1, n=100000 → 1168141 확인(MSVC /std:c++17 컴파일·실행).