<프로그래머스 C++> 멀리 뛰기 풀이 (피보나치)

문제

한 번에 1칸 또는 2칸을 뛸 수 있을 때, n칸을 이동하는 방법의 수를 1234567로 나눈 나머지를 return하는 문제이다.

---

풀이 아이디어

n칸에 도달하는 방법을 생각해보면, 마지막 점프가 1칸이었거나 2칸이었거나 둘 중 하나이다.

f(n) = f(n-1) + f(n-2)

이 문제를 보자마자 피보나치 수열의 점화식이 바로 떠올랐다.

 

초기값은

f(1) = 1  →  (1칸)
f(2) = 2  →  (1+1칸), (2칸)

이렇게 설정한다.

 

https://tjdgus123.tistory.com/95

<프로그래머스 C++> 피보나치 수 풀이(재귀 함수)

이 문제에서 푼 것 것처럼 반복문으로 해결한다.

재귀로 구현하면 직관적이지만 n이 최대 2000이므로 중복 계산이 폭발적으로 늘어나 시간 초과가 발생한다.

---

문제 풀이

#include <string>
#include <vector>
using namespace std;

long long solution(int n) {
    if(n <= 1) return n;

    long long a = 1, b = 1;
    for(int i = 2; i <= n; ++i)
    {
        long long c = (a + b) % 1234567;
        a = b;
        b = c;
    }
    return b;
}

---

코드 흐름

1. 초기값 설정

if(n <= 1) return n;
long long a = 1, b = 1;

a = f(1)

b = f(2)

루프 시작전, f(1)과 f(2)를 각각 담아둔다.

 

2. 반복문으로 피보나치 계산

for(int i = 2; i <= n; ++i)
{
    long long c = (a + b) % 1234567;
    a = b;
    b = c;
}

매 반복마다 세 변수가 한 칸씩 앞으로 당겨진다.

 

n = 4일때,

초기: a=1(f1), b=1(f2)

i=2: c=(1+1)%1234567=2  →  a=1, b=2   f(2)=2
i=3: c=(1+2)%1234567=3  →  a=2, b=3   f(3)=3
i=4: c=(2+3)%1234567=5  →  a=3, b=5   f(4)=5

루프가 i=n에서 끝날 때 b에 f(n)이 담겨있는 모습이다.

 

3. 결과

return b;

따라서 b를 리턴한다.

---

% 1234567을 매번 하는 이유

n이 최대 2000일 때, 피보나치 수는 천문학적으로 커져 long long으로도 표현이 불가능할 정도이다.

 

수학적으로도 (a + b) % m - ((a % m) + (b % m)) % m 이 성립하므로, 매번 나눠줘도 최종 결과가 같다.

그렇기 때문에 중간에 나눠주는 것이 overflow를 방지할 수도 있어 계속 나눠주는 것이다.

마지막에 한 번만 나누면
f(2000) = 천문학적으로 큰 수 → overflow → 틀린 답

매번 나누면
c = (a + b) % 1234567  // 항상 1234567 미만으로 유지 → 정확한 답

---

핵심 포인트

 

• 멀리 뛰기 경우의 수는 피보나치 수열과 동일한 점화식 f(n) = f(n-1) + f(n-2)을 따른다.
• 재귀 대신 반복문으로 O(n)에 해결한다.
• overflow 방지를 위해 매 반복마다 % 1234567을 적용한다.