[백준] 2331번: 반복수열 - C++

문제

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=5²+7²=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다.

 

입력

첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.

 

출력

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

---

1부터 1000000까지 vector형태의 배열을 만든 뒤, 모두 0으로 초기화해준다. 이 벡터는 방문횟수를 count 해주는 데 사용된다. DFS의 재귀적인 성질을 이용하여 A부터 방문하여 규칙에 따라 연산한 결과의 정점들을 차례차례 방문해가며 방문횟수를 세어준다. 수열을 구하면서 반복되는 수가 나왔을 때는 방문 횟수가 2 이상이 됐을때이므로, 이를 확인하여 처음으로 반복되는 수가 발생하였을 때 함수를 빠져나온다.

이후 한 번씩 방문한 정점의 개수가 반복수열의 길이가 된다.

 

코드

#include <cstdio>
#include <vector>
#include <cmath>
#define MAX 1000000

using namespace std;

vector<int> visited(MAX, 0);
void DFS(int num, int P);

int main(void) {
    int A, P;
    scanf("%d %d", &A, &P);
    DFS(A, P);
    
    int count = 0;
    for(int i = 0; i <= MAX; i++) {
        if(visited[i] == 1)
            count++;
        else
            continue;
    }

    printf("%d\n", count);
    return 0;
}

int calc(int A, int P) {
    int temp = A;
    int sum = 0;
    while(temp > 0) {
        sum += (int)(pow(temp % 10, P));
        temp /= 10;
    }
    return sum;
}

void DFS(int num, int P) {
    visited[num]++;
    if(visited[num] > 2) return; // 반복되는 수가 한바퀴 돌았을 때 멈춤
    DFS(calc(num, P), P);
}