[프로그래머스/C++ 문제 풀이] 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 이하인 자연수입니다.

입출력 예

 

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

---

문제 풀이

피보나치의 수는 대표적인 재귀함수의 예시 중 하나입니다.

 

예를들어 Fibo(5)를 구하기 위해서는 Fibo(4) + Fibo(3)이 필요하고, Fibo(4)를 구하기 위해서는 Fibo(2) + Fibo(3)이 필요하며 이런 식으로 반복되는 로직을 구현하기 위해 재귀함수를 사용했습니다.

 

하지만 위의 짧은 예시에서도 Fibo(3)은 2번이나 중첩되는 모습을 볼 수 있으며, 중복되는 수를 계속 계산해줘야 하기 때문에 n이 100,000까지 나올 수 있는 이번 문제에서는 일반적으로 사용하면 시간초과를 예상할 수 있습니다.

 

즉, 이미 나왔던 숫자를 배열에 저장해두고, 해당 숫자의 배열에 값이 존재하는 경우 중복 계산을 피하는 방식으로 시간복잡도를 크게 줄일 수 있습니다.

 

추가적으로 저는 1234567을 나눈 나머지를 구하기 위해 모든 답을 구한 뒤 1234567로 나눠줬지만, n이 100,000까지 되기에 값이 int의 최대 범위를 넘을 것을 생각하지 못해 1차 오답 처리를 받았습니다.

 

이후 Fibo() 함수 내부에서 미리 값을 초과하지 않도록 나눠주는 방식을 통해 문제를 해결하였습니다. 쉽고 많이 풀어본 문제였지만 꼼꼼하게 생각하는 습관을 길러야 할 것 같습니다. 

정답 코드

풀이 시간 : 4m 26s

#include <string>
#include <vector>

// Cache용 배열
int DP[100002];

using namespace std;

int Fibo(int n)
{
    // 피보나치의 경우 0은 0, 1은 1을 반환합니다.
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // 0과 1이 아닌 경우
    
    // 저장된 값이 없다면?
    if (DP[n] == 0)
    {
        // 해당 숫자의 값을 저장한 후 반환합니다.
        DP[n] = (Fibo(n - 2) + Fibo(n - 1)) % 1234567;
        return DP[n];
    }
    // 저장된 값이 있다면?
    else
    {
        // 불필요한 재귀 함수를 호출하지 않고 저장된 값을 호출합니다.
        return DP[n];
    }
}

int solution(int n) {
    int answer = Fibo(n);
    
    return answer;
}