[프로그래머스] - 피보나치 수(C++)

피보나치 수

 

문제 설명

피보나치 수는 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	result
3	2
5	5

 

시작 코드

#include <string>
#include <vector>

using namespace std;

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

 

나의 풀이

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n) {
    int cnt = 1;
    int tmp = 0;
    queue<int> q;
    
    q.push(0);
    q.push(1);
    
    while(cnt < n)
    {
        tmp = q.front() + q.back();
        if(tmp > 1234567) tmp -= 1234567;
        q.push(tmp);
        cnt++;
        q.pop();
    }
    return q.back();
}

 

코드 분석

cnt를 1, tmp를 0으로 초기화하고 queue를 생성합니다. q에 0과 1을 넣어주고, while문을 cnt가 n보다 커질때까지 실행합니다. while문 안에서는 tmp에 q의 첫번째 요소와 맨 뒤에 요소를 더한 값을 넣습니다. 이후 if문에서 tmp가 1234567보다 크가면 tmp를 1234567만큼 빼줍니다. if문을 빠져나오면 q에 tmp값을 넣고 cnt를 증가시키고 q를 pop합니다. while문을 빠져나오면 q의 마지막 요소를 리턴합니다.

 

풀이 설명

문제에서 요구하는 것은 2이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567로 나눈 나머지를 리턴하는 것입니다. 피보나치 수에 대한 설명은 문제에 나와있습니다. 이제 입출력 예 1번으로 코드를 실행시켜 보겠습니다.

 

n으로 3이 주어지고, cnt는 1, n은 3이므로 while문에 들어갑니다. q의 맨 앞과 맨 뒤에 요소는 처음에 0과 1이므로 tmp는 1이 됩니다. if문 조건에 충족하지 않으므로 넘어가고 q에 tmp값인 1을 넣어줍니다. cnt는 2가 되고 q를 pop하면 0이 제거됩니다. 그렇게 되면 q에는 1,1 이 남고, cnt는 2, tmp는 1인 상태입니다. 아직 cnt가 2이므로 다시 while문을 돌면 cnt는 3, tmp는 2가 되고 q에는 1,2가 남게됩니다. 이제 cnt와 n값이 같아졌기 때문에 while문에 들어가지 않고 q에 맨 뒤에 있는 2가 리턴됩니다.

 

중간에 있는 if문은 n값이 증가할수록 피보나치 수가 기하급수적으로 증가하므로, 문제에서 제시한 1234567을 넘지 않도록 처리하기 위한 조건입니다.

 

<NEXT>

오늘은 정답률 74% 연습문제 "피보나치 수" 문제를 풀어보았습니다. 다음에는 2017 팁스타운 문제 "짝지어 제거하기" 문제를 다뤄보도록 하겠습니다. 감사합니다.