문제
양의 정수 두 개를 입력받아, 각 수에 대해 "자리수의 제곱합" 연산을 반복 적용했을 때 두 수가 공통으로 도달하는 사이클까지의 거리를 구하는 문제다. 자리수의 제곱합을 반복하면 결국 1(Happy Number 사이클) 또는 89로 시작하는 사이클 중 하나에 수렴한다. 두 수가 같은 사이클에 속한다면 사이클 내 두 수 사이의 최단 거리를, 다른 사이클이면 0을 출력한다.
입력
두 정수 a, b를 반복 입력받는다. a + b == 0이면 종료한다.
출력
각 케이스에 대해 a b 거리를 출력한다. 두 수가 다른 사이클에 속하면 거리는 0이다.
예제
| 입력 | 출력 |
|---|---|
1 1 | 1 1 2 |
1 89 | 1 89 0 |
0 0 | (종료) |
풀이
자리수의 제곱합을 반복하면 반드시 아래 두 사이클 중 하나에 수렴함을 이용한다.
- 1-사이클 (Happy Number):
1 - 89-사이클:
89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 → ...(길이 8)
두 수가 각각 어느 사이클에 도달하는지, 사이클 내 어느 지점에 있는지를 추적해 거리를 계산한다.
- 두 사이클의 원소 배열
arr[9] = {89, 145, 42, 20, 4, 16, 37, 58, 1}을 미리 저장한다. cal(n): n의 각 자리수를 제곱해 합산하는 함수in(n): n이 사이클 원소 중 하나인지 확인하는 함수- a와 b 각각에 대해 사이클에 도달할 때까지의 경로를 벡터
aa,bb에 저장한다. - 두 수가 도달한 사이클이 다르면(하나는 1-사이클, 다른 하나는 89-사이클)
0을 출력한다. - 같은 사이클이면:
a == b이면 두 경로의 꼬리에서 공통 구간을 제거해 최단 거리를 계산한다.a != b이면(둘 다 89-사이클이지만 다른 지점) 사이클 배열에서 두 인덱스의 차이를 구해 거리를 계산한다.
핵심 아이디어: 자리수의 제곱합 반복은 반드시 길이 1(Happy Number, 값 1) 또는 길이 8(89-사이클)에 수렴한다. 이를 미리 알고 있으면 사이클까지의 경로를 추적해 두 수 간의 최단 거리를 O(log n) 수준의 짧은 반복으로 구할 수 있다.
코드
#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;
}복잡도
- 시간: O(log N) — 각 수에서 사이클 도달까지의 반복 횟수는 자릿수에 비례하며 매우 빠르게 수렴
- 공간: O(log N) — 사이클 도달 전까지의 경로를 벡터에 저장