백준 9471번 (피사노 주기, C++) [BAEKJOON]

피사노 주기

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

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초128 MB136796382673.422%

문제

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

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

n12345678910
F(n)11235813213455
F(n) mod 1111235821010

나머지를 이용해서 만든 수열은 주기가 나타날 수 있다.

k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10임을 알 수 있다.

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

m이 주어졌을 때, k(m)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 P가 주어진다.

각 테스트 케이스는 N과 M으로 이루어져 있다.

N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다.

출력

각 테스트 케이스마다 테스트 케이스 번호를 출력하고 k(M)을 출력한다.

제한

예제 입력 1

5
1 4
2 5
3 11
4 123456
5 987654

예제 출력 1

1 6
2 20
3 10
4 15456
5 332808

출처

ICPC > Regionals > North America > Greater New York Region > 2013 Greater New York Programming Contest D번

알고리즘 분류


처음 문제를 확인하고 증명이 있어 이걸 이용하여 문제의 답을 찾는 것인가 생각했다.

해당 식들을 구현하면서 이건 아닌 것 같다고 생각했고 다른 블로그를 보면서

이러한 문제는 어떤 식으로 접근하는지 확인하였다.

포인트는 피사노 주기는 피보나치수열을 M으로 나눴을 때 이 나머지가 규칙성을 가지고 반복된다는 것

피보나치수열은 F(0) = 0, F(1) = 1 … 나눌 숫자 M >= 2 조건이므로

이후의 연산에서 나머지가 0, 1 순서로 나온다면 주기가 반복된다는 뜻이다.

피보나치수열을 M으로 나누어주고 나머지가 0 과 1이 순서대로 나올 때 까지 반복해주면서

주기를 카운트 하면 문제를 해결 할 수 있다.

참고 : https://en.wikipedia.org/wiki/Pisano_period <- 피사노의 주기 위키

통과된 코드

#include <iostream>
#include <list>

using namespace std;

list<pair<int, int>> tcList;
list<pair<int, int>> resultList;

// 문제의 입력을 처리하는 함수
void GetInput()
{
	int N;
	cin >> N;
	pair<int, int> tempPair;
	while (N-- > 0) {
		cin >> tempPair.first >> tempPair.second;
		tcList.push_back(tempPair);
	}
}

// 피사노의 주기를 확인하는 함수
int PeriodOfPisano(int tc)
{
	int a = 0, b = 1, cnt = 0, temp =0;

	// 주기가 나올때까지 반복해준다.
	while (true)
	{
		// 모듈러 산술 분배법칙
		temp = ((a % tc) + (b % tc)) % tc;
		a = b;
		b = temp;
		cnt++; // 주기가 얼마인지 체크

		// 나머지로 나눈 값이 처음과 같은 0과 1의 순서로 나온다면, 다시 주기가 반복된다는 뜻
		// (F2 = F1 + F0 , 나머지도 계속 반복을 하게 된다.)
		if (a == 0 && b == 1) break; 
	}

	return cnt; // 주기 리턴
}

int main()
{
	GetInput(); // 입력 받기
	
	// 테스트 케이스만큼 순회 
	for (auto iter = tcList.begin(); iter != tcList.end(); iter++) { // 결과값 출력
		cout << iter->first << " " << PeriodOfPisano(iter->second) << "\n"; 
	}

	return 0;
}

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

Scroll to Top