백준 2331번 반복수열

문제

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

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

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=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)가 주어진다.

출력

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

 

 

 

 

BFS는 경로찾기에 주로 쓰이고 이제 익숙한데 , DFS에 아직 취약한것 같음. DFS의 매개변수로 사용할 것이 무엇인지 찾는 연습 필요.. 그리고 복잡한 i to string 이라던지 하는 알고리즘은 거의 안쓰는 것 같음.

 

 

 

 

 

 

#include <iostream>
#include <cmath>
using namespace std;

int P;
int visit[300000];

int DFS(int num)
{
    visit[num]++;
    
    if(visit[num] >= 3)
    return 0;
    
    int temp = 0;

while(num)
{
temp += pow((num % 10),P);
num = num /10 ;
}

DFS(temp);
}


int main(void)
{


ios_base::sync_with_stdio(0);

    cin.tie(0);
    
    
int num;
int count = 0;

cin >> num >> P;

DFS(num);

for(int i = 0; i< 300000; i++)
{
if(visit[i] == 1)
{

count++;
     }
}

cout << count << endl;




}