백준[2331] - 반복 수열

문제

백준 2331 문제 보기

접근 방법

최악의 상황으로 메모리를 잡고 연산을 계산해보니 시간 초과는 나지 않을 것 같아 배열을 최대로 잡고 풀었다. 먼저 계속 각 자리를 제곱해 더한 수를 따로 배열에 저장하고 계산 진행하다 추후에 반복된 숫자가 나오면 완전 탐색을 빠져 나간다.
dfs함수 안에서 cnt를 세는 건 참고로 안해도 된다.

코드

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

string A;
int P, E;
vector visited;
int D[600000];

int dfs(string num) {

    int temp = 0;
    for(int i = 0; i < num.length(); i ++) {
        temp += pow(num[i] - '0', P);
    }

    int cnt = 0;
    if(D[temp]) {
        E = temp;
        for(int i = 0; i < 600000; i ++) {
            if(D[i]) {
                cnt ++;
            }
        }
        return cnt;
    } else {
        D[temp] = 1;
        visited.push_back(temp);
        return dfs(to_string(temp));
    }
};

int main() {

    cin >> A >> P;

    memset(D, 0, sizeof(D));

    int index = stoi(A);
    D[index] = 1;
    visited.push_back(index);
    dfs(A);

    int cnt = 0;
    for(int i = 0; i < visited.size(); i ++) {
        if(visited[i] == E){
            cout << cnt;
        } else {
            cnt ++;
        }
    }

    return 0;
}