[백준] 알고리즘 2331번 - 반복수열 문제

#include <bits/stdc++.h>
using namespace std;
int check[3000001];
int p;
void dfs(int x) {
    check[x]++;
    if (check[x] == 3) return;
    int sum = 0;
    while (x != 0) {
        sum += pow(x % 10,p);
        x /= 10;
    }
    dfs(sum);
}
int main(){
    int n,ans=0;
    cin >> n >> p;
    dfs(n);
    for (int i = 0; i < 300001;i++) {
        if (check[i] == 1) ans++;
    }
    cout << ans;
}

이 문제는 간단하게 DFS를 이용하여 풀 수 있다.

먼저 최대값을 계산하여 배열 범위정도를 판단할 수 있다.

그런다음 check=1 인 경우는 한번 방문했다는 것을 의미하고

check=2 인 경우는 두번 방문

check=3 인 경우는 하나의 사이클을 이루고 있다는 것을 의미한다.

즉 문제에서 원하는 답은 check=1인 것의 개수를 요구하고 있다.