[2025.02.17] 피보나치 수

문제 설명

피보나치 수는 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이하인 자연수입니다.

 

 

입출력 예

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

 

 

문제 풀이

풀이 언어 : C++

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

int solution(int n) {
    int answer = 0;
    
    vector<long long> fibNum;
    fibNum.push_back(0);
    fibNum.push_back(1);
    
    for(int i=2; i<=n; i++)
    {
        fibNum.push_back((fibNum[i-1]%1234567+fibNum[i-2]%1234567)%1234567);
    }
    
    answer=fibNum[n];
    return answer;
}

문제도 길지 않고 결론적으로 코드도 길지 않지만 생각보다 많은 생각을 하게 되었던 문제였다. 아래 오답노트를 보면 알 수 있지만 문제에서 말하는대로 구현한다고 해서 풀리는 문제가 아니었다.

 

말하는대로 구현하고자 하면 먼저 fibNum이라는 벡터를 선언하고 0번째와 1번째에 각각 0과 1을 넣기위해 push_back 해준다. 그리고 반복문을 돌리면서 알맞은 수를 push_back 해준다. fibNum(i-1)+fibNum(i-2)의 결과를 push_back 해주어야 하는데 이렇게 문제에 나온 그대로 계산하면 7개의 테스트케이스에서 오답이라는 글자를 만나야만 한다. 뒤로 갈 수록 숫자가 너무 커지기 때문인데 숫자를 줄이기 위해서 한 가지 처리를 해준다. 결과값으로 1234567로 나눈 나머지를 요구하였으니 fibNum[i-1]과 fibNum[i-2]에 각각 1234567로 나눈 나머지의 계산을 해주고 두 수를 더한 값에도 나머지 연산을 해주는 것이다.

 

마지막으로 정답값 answer을 반환해주면 된다.

 

참고 사항

나머지 연산에는 아래와 같은 특징이 있다. 

(a + b) % m = ((a % m) + (b % m)) %m

 

 

오답 노트

fibNum 벡터의 데이터 타입을 int로 해도 long으로 해도, long long으로 해도 피보나치 수를 계산하다가 그 범위를 넘어가는 건 막을 수 없었다. 아무리 데이터형을 바꿔도 해결하지 못하던 것을 나머지 연산의 특징을 이용해 해결할 수 있었다. 각각의 수에 나머지 연산이 들어가고 마지막에도 나머지 연산을 해주니 연산 중 값이 데이터형의 크기를 넘어가지 않아서 오류 없이 풀이할 수 있었다.

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

int solution(int n) {
    int answer = 0;
    
    vector<long long> fibNum;
    fibNum.push_back(0);
    fibNum.push_back(1);
    
    for(int i=2; i<=n; i++)
    {
        fibNum.push_back(fibNum[i-1]+fibNum[i-2]);
    }
    
    answer=fibNum[n]%1234567;
    return answer;
}

 

 

문제 링크

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

프로그래머스