[C++/Programmers] Lv2. 피보나치 수

Lv2 문제이다.

 

단순하게 피보나치 수를 구하는 함수를 만들어 주면 된다.

 

---

생각 해 보기

 

피보나치 수는 기본적으로 재귀함수를 이용한다.

 

그런데 처음에 재귀함수를 사용하니 시간초과가 나게 되어 아래와 같이 동적 프로그래밍을 사용하였다.

 

#include <string>
#include <vector>

using namespace std;

int func(int input,vector<int>& info){
    
    info[0] = 0;
    info[1] = 1;
    
    for(int i = 2;i<info.size();i++){ // 저장을 해 준다.
        info[i] = info[i-1] + info[i-2];
    }
    
    return info[input];
}

int solution(int n) {
    int answer = 0;
    vector<int> saveInfo(100001);
    answer = func(n,saveInfo) % 1234567;
    
    return answer;
}

그런데 케이스 7번부터 실패를 하게 되는 것이다.

---

문제 발생

 

맞는 것 같은데 왜 틀리게 될까 고민하면서 질문하기 란을 보았다.

 

처음에는 자료형 문제라는 진단이 나오게 되었다. n의 범위가 100,000까지인데 피보나치 수로 계속 더해 가게 되면 int의 범위를 넘어서는 문제가 생기게 된다는 것이다.

 

그런데 이 점은 문제에서 힌트를 주었다.

 

단순 피보나치 수의 결과를 출력하는 것이 아닌 1234567로 나눈 나머지를 출력하라는 의미는 int의 범위를 넘지 않게 해 주려는 배려인 것이다.

 

7번부터는 큰 수가 들어가기 때문에 동적 프로그래밍 배열에 저장할 때도 1234567로 나누어서 저장 해 주어야 한다.

 

그래야 int 배열 안에 있는 값으로 차근 차근 정리가 된다.

 

결과 값에서만 1234567로 나눈 나머지를 넣게 되면 이미 그 전에 큰 값으로 더해진 값들이 int 범위를 넘는게 생길 수 있기 때문에 원하는 값이 나오지 않게 된다.

 

#include <string>
#include <vector>

using namespace std;

int func(int input,vector<int>& info){
    
    info[0] = 0;
    info[1] = 1;
    
    for(int i = 2;i<info.size();i++){ // 저장을 해 준다.
        info[i] = info[i-1] % 1234567 + info[i-2] % 1234567;
    }
    
    return info[input] % 1234567;
}

int solution(int n) {
    int answer = 0;
    vector<int> saveInfo(100001);
    answer = func(n,saveInfo) % 1234567;
    
    return answer;
}

이렇게 해 주면 성공하게 된다.