[C++] BOJ 2331 반복수열

문제 출처

백준 온라인 저지

https://www.acmicpc.net/problem/2331

2331번: 반복수열

 

문제 

 

입 / 출력

 

풀이

DFS 알고리즘을 사용해서 풀 수 있다.

A의 각 자리의 숫자를 P번 곱한 수들의 합한 수를 표시하고, 이미 방문한 적이 있을 경우 재귀 함수를 탈출한 뒤,

반복문을 사용해서 한 번만 방문한 숫자까지의 수를 구한 뒤 출력한다.

 

코드

#include <iostream>
#include <math.h>

using namespace std;

const int MAX = 300000 + 1;
int A, P, cnt = 0;
int visited[MAX];

void dfs(int A, int P) {
  visited[A]++;
  if (visited[A] == 3)
    return;
  int temp = 0;
  while (A != 0) {
    temp += (int)pow(A % 10, P);
    A /= 10;
  }

  dfs(temp, P);
}

int main() {
  cin >> A >> P;
  dfs(A, P);
  for (int i = 0; i < MAX; i++)
    if (visited[i] == 1)
      cnt++;

  cout << cnt;
}