[BAEKJOON] 백준 그래프 2331 :: 반복수열

 

💬  문제 설명

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

* 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]의 네 개의 수가 남게 된다.

 

🔨  입출력 예

입력 

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

   

출력

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

 

예제 입력 1)

57 2

 

예제 출력 1)

4

 

✨  Idea

 DFS 스택처럼 이용한다.

위와 같이 37처럼 겹치는 부분이 있을 때, answer = list.indexOf(37)

​

💻  Main.java

/* 백준 그래프 - 2331 :: 반복수열 */
import java.util.*;

public class Main {
	static int answer = 0;
	static ArrayList<Integer> list = new ArrayList<>();
	
	static void DFS(String A, int P) {
		// D[n-1]의 각 자리의 숫자를 p번 곱한 수들의 합 구하기
		int total = 0;
		for(char c : A.toCharArray()) {
			int tmp = 1;
			for(int i = 0; i < P; i++) {
				tmp *=  c - '0';
			}
			total += tmp;
		}
		
		// 반복 수열을 발견하면
		if(list.contains(total)) {
			// 반복 수열의 처음 인덱스 값 리턴
			answer = list.indexOf(total);
		}
		else {
			list.add(total);
			DFS(String.valueOf(total), P);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String A = sc.next();
		int P = sc.nextInt();
		
		list.add(Integer.parseInt(A));
		DFS(A, P);
		System.out.println(answer);
		sc.close();
	}
}