취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25802번 문제인 Fiborooji Sequence이다.
문제는 아래 링크를 확인하자.

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

첫 두 수를 X와 Y라 할 때, 바로 다음 두 항 x와 y부터 x=X, y=Y가 될 때까지 x는 y로, y는 (x+y)%10으로 바꿔나가면서 그 바꿔나가는 횟수를 세는 것으로 문제를 해결할 수 있다. 이 구현은 while문을 이용하여 간단히 할 수 있다.

이와 같은 연산으로 x와 y가 첫 두 수 X와 Y로 항상 돌아오는 것은 문제가 보장해주고 있고(피사노 주기(Pisano period)를 참고하자), 이러한 연산이 제한시간 내로 끝난다는 것은 비둘기집의 원리를 이용해 쉽게 보일 수 있다. 즉, 서로 다른 순서쌍 (x,y)는 100가지이므로 100회 이내로 연산이 끝날 수밖에 없다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

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

	int X, Y; cin >> X >> Y;
	
	int ans = 3;
	int x = Y, y = (X + Y) % 10;
	while (x != X || y != Y) {
		ans++;
		int yy = (x + y) % 10;
		x = y; y = yy;
	}

	cout << ans;
}