백준 9471번 : 피사노 주기

풀고 나서 허무했다. 너무 어렵게 생각한 것 같다.

피사노 주기 문제의 일부분

  되게 뭐가 있을 것처럼 설명해놨잖아! 그래서 막 m이 2의 제곱수인지 5의 제곱수인지 등등을 파악해서 경우의 수를 나눠서 구해야 하는 줄 알았다.... 하지만 그냥 Brute Force 였구요~~ do - while 문을 실제 문제에서 한 번 사용해봤다는 점에서 조금 유익하긴 했다.

 

  풀이 방법은 결국 주기만 구하면 되는 것이기 때문에 첫 항과 두번째 항을 설정하고 while 문을 돌려서 첫째 둘째항과 동일한 항이 나올 때까지 count를 증가시킨다. 동일한 항이 나오면 그 때 count가 곧 주기이므로 그 값을 리턴한다.

 

#include <stdio.h>
#include <iostream>
 
using namespace std;
 
int p;

int fisano(int div)
{
    int first = 1;
    int second = 1;
    int count = 0;
    
    do
    {
        int third = first + second;
        first = second;
        second = third % div;
        count += 1;
    }
    while(first != 1 || second != 1);
    
    return count;
}

int main() {
    cin >> p;
 
    for(int i = 0; i < p; i++)
    {
        int n, m;
        cin >> n >> m;
        
        cout << n << " " << fisano(m) << "\n";
    }
 
    return 0;
}