[백준][C++] 9471번: 피사노 주기 <193>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

생각의 흐름

피보나치 수열을 구하는 방식으로 수들을 구를 구하되, 나머지 연산을 중심으로 생각해야 한다.

나머지들이 얼마나 부분수열을 이루는지 알아야 하기 때문이다.

 

주어진 M으로 나눠주면서 vector에 push 하였고, 벡터의 맨 마지막 원소가 0 그리고 마지막 바로 한칸 앞 원소가 1 일 때 종료한다. 
다시 피보나치 수열이 1부터 반복하게 된다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;

int P;

int pisano(int num){
    vector<int> vec;

    vec.push_back(0);
    vec.push_back(1); // 1일떄
    vec.push_back(1); // 2일때

    int i;
    for(i = 2; ;){
        vec.push_back((vec[i] + vec[i-1]) % num);
        i++;
        if(vec[i] == 0 && vec[i-1] == 1) break;
    }
    return i;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> P;
    int N, M;
    for(int i = 0; i < P; i++){
        cin >> N >> M;
        cout << N << " " << pisano(M) << "\n";
    }

    return 0;
}