이 문제는 그래프(Graph) 문제라고 보기에는 다소 무리가 있어 보이긴 한다.
정점과 간선 정보를 바탕으로 데이터를 처리하는 방식인 Graph 구조라기 보다 연산을 통해 구성되는 숫자들을 하나의 정점으로 보고 방문 여부, 즉 생성 여부만을 체크하다가 이미 생성된 숫자가 2번째 등장하는 지점부터는 반복적으로 수열이 진행될테니 이 때 이 반복 수열에 포함되지 않는 수열의 개수를 묻는 문제이다.
주어지는 정점 정보도 없고, 간선 정보도 없다. 연산의 방식이 문제 풀이에 있어 가장 중요한 키(key)이다.
임의의 숫자를 특정한 연산을 통해 다음에 연결되는 숫자를 생산하게 되는데, 이 연산에 대한 방법은 문제에서 제공하고 있다.
주어지는 숫자에서 각 자리의 숫자들을 주어지는 횟수(p)만큼 거듭제곱을 하여 합산하는 방식이다.
(e.g)
57 2 → “5”를 2 제곱한 수 + “7”를 2 제곱한 수 = $5^2+7^2 = 74$ 가 된다.
74 2 → “7”을 2 제곱한 수 + “4”를 2 제곱한 수 = $7^2+4^2 = 65$ 가 된다.
문제의 내용을 도식화 시키면 다음과 같다.
57 → 74 → 65 → 61 → 37 → … 순차적으로 주어진 연산 결과 숫자를 만들어 나간다.
이 때, 주어진 연산 만큼이나 중요한 것이 순번이다.
57(1) → 74(2) → 65(3) → 61(4) → 37(5) → …
이렇게 연산의 결과값을 만들어 나가는 과정에서 순번을 함께 구성시켜 나간다.
이렇게 구성해 나가는 과정에서 이미 생성된 숫자 중에 다시 연산의 결과로 만들어지는 숫자가 있다면 그 숫자부터는 반복 수열이 계속 전개되는 것이기 때문에 그 숫자 이전에 구성된 숫자들은 이 반복 수열에 참여하지 않는 숫자들이다.
그 숫자들의 갯수가 문제에서 요구하는 값이다.
각 숫자를 만들어 나가는 과정에서 순번도 함께 기록하고 있다면 37(5) → ... 37(5) 와 같이 다시 등장하는 숫자의 순번 앞의 수들의 개수이므로 (순번 - 1)을 통해 정답을 구할 수 있다.
이 방식에 따라 57부터 시작해서 2제곱씩 하는 수열에서 반복 수열에 포함되지 않는 수열의 길이는 5 - 1 = 4가 된다.