---

문제

1. 문제
   다음과 같이 정의된 수열이 있다.
   D[1] = A
   D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합
   예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

   이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다.

2. 입력
   첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.

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

4. 예제 입력 1
   57 2

5. 예제 출력 1
   4

---

순서

1. A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5) 입력받기
2. 배열생성 D[A] = count++;
   • 초기값 설정 -> D[57] = 1
   • 이후 진행 ---> D[74] = 2 , D[65] = 3 , ...
3. dfs 생성
   • 숫자변환
     A = A1 P+ A2 a+A3 a...
   • 조건
     • D[A] == 0 이면 방문한 적 없는 노드이므로
       D[A] = count++;
     • D[A] != 0 이면 방문한 적 있는 노드이므로
       return count;
   • dfs 재귀호출
4. 출력

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int a = Integer.parseInt(st.nextToken());
		int p = Integer.parseInt(st.nextToken()); 

		int count = 1;
		int[] d = new int[250000];
		d[a] = count++;
		
		int result = dfs(a, p, d, count);
		System.out.println(result);
	}
	
	public static int dfs(int a, int p, int[] d,int count) {
		String num = Integer.toString(a);
		int x = 0;
		for(int i = 0; i < num.length(); i++) {
			x += Math.pow(num.charAt(i) - '0', p);
		};
		
		if(d[x] != 0) {
			return d[x] - 1;
		}
		d[x] = count++;
		
		return dfs(x, p, d, count);
	}
}