백준 2331번 : 반복수열 C++

BOJ 2331번 반복수열 문제

이 문제는 DFS로 풀었다.

각 자리 숫자를 P 제곱한 후 더한게 다음 숫자가 되는 방식인데, 중간에 계속해서 반복되는 구간이 나타난다.

그 구간에 포함되지 않는 숫자들의 갯수를 구하는 문제이다.

자꾸 pow(5, 2)를 24로 출력해서 뭐가 잘못됐나 했는데 pow() 함수의 return type이 실수형이었다.

그래서 반올림해서 정수형으로 변환했다.

2331.cpp

#include <bits/stdc++.h>
using namespace std;
int result;
int visitCount[1000000];

int mult(int A, int P) {
    int next = 0;
    while (A > 0) {
        next += (int)floor(pow(A % 10, P)+0.5);
        A /= 10;
    }
    return next;
}

void DFS(int A, int P) {
    visitCount[A]++;
    if (visitCount[A] > 2) {
        return;
    }
    DFS(mult(A, P), P);
}

int main() {
    int A, P;
    cin >> A >> P;
    DFS(A, P);

    for (int i = 0; i < 100000; i++) {
        if (visitCount[i] == 1) {
            result++;
        }
    }

    cout << result;
}