[C/C++] 백준 9471번 - 피사노 주기

✏️  문제 링크

https://www.acmicpc.net/problem/9471

 

✏️ 문제 설명

✏️ 로직(처음)

1. 피사노 주기 찾아보기
2. arr[i] = (arr[i-1] + arr[i-2]) % m
3. arr[i-1]과 arr[i-2]가 1일 때의 반복횟수를 리턴해준다
4. 배열로 하니 메모리도 많이 사용하고 문제에서 요구하는 사항을 맞추지 못할 것 같아서 단순 반복문 이용

✏️ 코드

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

long long arr[1000001];
long long int fun(long long int m) {

    if (m==2)
        return 3;
    if (m==3)
        return 8;
    for (long long i = 3; i <= m * m; i++) {
        arr[i] = (arr[i - 1] % m + arr[i - 2] % m) % m;
        if (arr[i-1] ==1 && arr[i - 2] == 1 && i>3) {
            return i-3;
        }
    }
}

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

    int t, n;
    long long int m;
    cin>>t;

    arr[1]=1;
    arr[2]=1;

    while(t--) {
        cin >> n >> m;
        int rate = fun(m);
        cout << n << " " << rate << "\\n";
    }
}

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

long long arr[1000001];
long long int find_pisano(long long int m) {

    if (m==2)
        return 3;
    if (m==3)
        return 8;
    for (long long i = 3; i <= m * m; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % m;
        if (arr[i-1] ==1 && arr[i - 2] == 1 && i>3) {
            return i-3;
        }
    }
}

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

    int t, n;
    long long int m;
    cin>>t;

    arr[1]=1;
    arr[2]=1;

    while(t--) {
        cin >> n >> m;
        cout << n << " " << find_pisano(m) << "\\n";
    }
}

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

long long int find_pisano(long long int m) {
    long long a = 1, b = 1;
    long long rate = 0;
    while (true) {
        long long c = (a + b) % m;
        a = b;
        b = c;
        rate ++;
        if (a==1 && b==1)
            return rate;
    }
}

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

    int t, n;
    long long int m;
    cin >> t;

    while (t--) {
        cin >> n >> m;
        cout << n << " " << find_pisano(m) << "\\n";
    }
}

✏️ 느낀 점

음 솔직히 이게 왜 맞는지를 모르겠다. 피사노 주기는 m≤ m^2 - 1까지를 허용하는데 내가 한 경우에서는 m이 1000000까지인 경우만 계산이 되는데 저때까지 주기를 못 구하면 틀리는 풀이가 아닌가? 세 번째 풀이가 맞는 풀이 같음

 

✏️ 결과

다른사람들을 보니 보통 4ms가 걸려서 내 풀이를 다시 보니 굳이 나머지 연산을 한 줄에서 3번을 할 필요가 없어 보여서 나머지 연산 횟수를 줄였더니 8ms가 줄었다.