[Java] 백준 2331번: 반복수열

문제

💡 일단 생각하기!

지옥의 알고리즘 다시 시작.
수열에서 반복되는 수가 처음 나온 순간 그 이후에도 같은 수가 나올 수 밖에 없다. 이것을 이용해서 DFS로 문제를 풀이했다.
num은 항상 같은 개수의 자리 수가 들어갈 수 없으므로 while문에서 Math.pow를 이용해서 값을 계산해준다.
이때, A가 9999, P가 5일 경우가 최대 값이고 이 값은 236196이므로 배열의 크기를 이에 맞게 설정해준다. 이 부분을 고려하지 않아 수많은 런타임 에러를 만났다 (바보)

풀이

import java.io.*;
import java.util.*;

/**
 * 백준 2331번 반복수열
 * 메모리 : 12984KB 시간 : 68ms
 * 
 * 아이디어
 * - DFS 사용
 * - 거듭제곱 계산을 위해 Math.pow 함수 사용
 * - num에 항상 같은 자리의 수가 들어갈 수 없으므로 while문에서 계산하여 더하도록 함
 * - 최대 값 고려를 하지 않아 계속 런타임 에러가 남 (ㅜㅜ)
 * - 최대일 경우는 (9999, 5)로 236196이 되므로 이에 맞게 배열의 크기 설정
 */

public class BJ_2331_반복수열_김유나 {
	static int A, P, nums = 0, order[];
	static boolean isVisited[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		A = Integer.parseInt(st.nextToken());
		P = Integer.parseInt(st.nextToken());

		// (9999, 5)일 경우 최대 수는 236196이므로 30만으로 잡기
		isVisited = new boolean[300000];
		order = new int[300000];

		dfs(A, 0);

		System.out.println(nums);
	}

	static void dfs(int num, int count) {
		if (!isVisited[num]) {
			isVisited[num] = true;
			order[count] = num;
		}

		else { // 반복된 숫자일 경우
			for (int i = 0; i <= count; i++) {
				if (order[i] == num) {
					nums = i; // 해당 순서를 찾아 return
					break;
				}
			}
			return;
		}

		int sum = 0;
		while (num > 0) {
			// 각 자리 거듭제곱 구하여 더하기
			sum += Math.pow(num % 10, P);
			num /= 10;
		}

		dfs(sum, count + 1);
	}
}