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

 

 🔗 문제 링크 : https://www.acmicpc.net/problem/9471 

 

---

 

문제

1960년, IBM의 직원 Donald Wall은 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다.

예를 들어, 피보나치 수열의 처음 10개를 11로 나눈 예는 다음과 같다.

피보나치 수열을 11로 나눈 예시

나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10 임을 알 수 있다.

Wall은 아래와 같은 여러 가지 성질도 증명했다.

m > 2인 경우에 k(m)은 짝수이다.
임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.
k(m) ≤ m2 - 1
k(2n) = 3×2(n-1)
k(5n) = 4×5n
k(2×5n) = 6n
n > 2라면, k(10n) = 15×10(n-1)
m이 주어졌을 때, k(m)을 구하는 프로그램을 작성하시오.

 

 

 

 

 

입출력 예시

입출력 예시 및 제한 사항

 

입출력 예시

 

 

 

---

 

풀이 

"피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다."

즉 위 문제에서 예시로 나온 표를 보면, 주기의 시작과 두 번째는 항상 1로 시작한다는 것을 알 수 있다.

 

 

 

💀 신기한 만큼 의심도 생기니까(?) 하나 더 테스트를 해보았다.

 

위 사진처럼, 문제에서 1 4 를 입력하면 1 6 을 출력하는 예제가 있었으니

피보나치 수열을 4로 나눈 나머지의 주기가 6 임을 예상할 수 있다.

 

피보나치 수열을 4로 나눈 나머지를 표로 나타내보았다.

피보나치 수열을 4로 나눈 나머지

 

주기의 시작과 두 번째 값은 항상 1 1 인 것을 알 수 있고, 예상한 대로 주기 6을 갖는다.

 

결국,  1 이 두 번 연속으로 나왔다면, 주기를 찾은 셈이다.

 

#include <iostream>
using namespace std;

int pisano(int m) {
    int previous = 1;
    int current = 1;
    int temp;

    for (int i = 0; i < m * m; ++i) {
        temp = (previous + current) % m;
        previous = current;
        current = temp;

        //. 주기를 찾은 경우
        if (previous == 1 && current == 1) {
            return i + 1;
        }
    }

    return 0;
}

int main() {
    int p;
    scanf("%d", &p);

    for (int i = 0; i < p; ++i) {
        int n, m;
        scanf("%d %d", &n, &m);

        printf("%d %d \n", n, pisano(m));
    }

    return 0;
}

 

(previous + current) % m

• pisano 함수의 for문 첫 번째 줄  
  • 모듈러 연산을 이용했기 때문에 피보나치 수를 직접적으로 사용하지 않고 연산할 수 있다.
  • 모듈러 연산의 성질 : (A + B) % C의 값은 ( ( A % C ) + ( B % C) ) % C 와 같다.
  • 피보나치 수열에서 다음 항을 계산할 때, 이전 두 항의 합을 구한 후 m으로 나누는 것은, 이전 두 항 각각을 m으로 나눈 나머지의 합을 m으로 나눈 것과 동일하다.

 

모듈러 산술의 자세한 내용은 아래 링크를 참고하자.

 

🔗 참고 : 모듈러 산술 - 위키백과 

모듈러 산술 - 위키백과, 우리 모두의 백과사전

 

 

 

---