백준 4881번: 자리수의 제곱

백준 온라인 저지(BOJ) 4881번 문제

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

1. 문제 요약

각 자리수를 제곱하여 더하여 만들어지는 수열이 있다.

초기 숫자 두 개가 주어질 때, 같은 숫자가 나올 때까지의 수열의 길이의 합이 가장 작을 때 그 합은 얼마인가?

2. 알고리즘

문제에서 두 개의 사이클이 소개되었다.

하나는 89, 145, 42, 20, 4, 16, 37, 58이고 하나는 1이다.

따로 계산을 해보면 알겠지만 이 두 개의 사이클이 유일한 사이클이다.

따라서 수열이 저 사이클에 포함될 때 까지 계산해준 뒤,

서로 다른 사이클이면 불가능

같은 사이클일 경우, 첫 도착지점이 같으면 공통 부분을 소거해주고

첫 도착지점이 다를 경우 (ex 89, 37처럼 될 경우) 짧은 방향으로 사이클을 돌아야 한다

(위 예시에서는 37에서 출발해서 37->58->89로 가야 한다)

3. 코드

#include <iostream>
#include <vector>

using namespace std;

int arr[9] = { 89, 145, 42, 20, 4, 16, 37, 58, 1 };

int cal(int n) {
	int r = 0;
	while (n) {
		r += (n % 10) * (n % 10);
		n /= 10;
	}
	return r;
}

bool in(int n) {
	for (int i = 0; i < 9; ++i) {
		if (n == arr[i]) return true;
	}
	return false;
}

int main() {
	int a, b;
	while (true) {
		scanf("%d %d", &a, &b);
		if (a + b == 0) break;
		printf("%d %d ", a, b);
		vector<int> aa;
		vector<int> bb;
		while (in(a) == false) {
			aa.push_back(a);
			a = cal(a);
		}
		while (in(b) == false) {
			bb.push_back(b);
			b = cal(b);
		}

		if (a == 1 ^ b == 1) {
			printf("0\n");
			continue;
		}
		
		if (a == b) {
			while (!aa.empty() && !bb.empty() && aa.back() == bb.back()) {
				aa.pop_back();
				bb.pop_back();
			}
			printf("%d\n", aa.size() + bb.size() + 2);
		}
		else {
			int ai, bi;
			for (int i = 0; i < 8; ++i) {
				if (a == arr[i]) ai = i;
				if (b == arr[i]) bi = i;
			}
			int r = ai > bi ? ai - bi : bi - ai;
			printf("%d\n", aa.size() + bb.size() + 2 + (r > 4 ? 8 - r : r));
		}
	}

	return 0;
}