[백준] 2331. 반복수열 (java)

📖 문제

https://www.acmicpc.net/problem/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. A를 char[] 로 바꾼다.
2. P만큼 곱하고 더한 값을 다시 A에 저장한 후 ArrayList에 넣는다.
3. A가 이미 ArrayList에 있다면 반복문을 종료한다
4. ArrayList에서 A의 첫번째 인덱스를 찾아 답으로 출력한다

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int A = scan.nextInt();
		int P = scan.nextInt();
		ArrayList<Integer> al = new ArrayList<>();

		while (!al.contains(A)) {
			al.add(A);
			char[] c = String.valueOf(A).toCharArray();
			A = 0;
			for (int i = 0; i < c.length; i++) {
				int s = 1;
				for (int j = 0; j < P; j++) {
					s *= c[i] - '0';
				}
				A += s;
			}
		}

		int idx = al.indexOf(A);
		System.out.println(idx);
	}

}

---

나왔다 dfs가 dfs인 줄 모르는 문제..

이게 왜 이 카테고리에 있어요? 하면서 처음에 겁나 빠르게 구현 문제처럼 품

dfs로 푼 사람들 풀이 봤는데 visited=true면 멈추도록 했던데

그냥 이거나.. 그거나.. 거기서거기 아니냐는 생각으로 직접 풀어보진 않았습니다..

사실 boolean 자료형 최댓값으로 배열을 만들어 둬야 하는데 그걸 못하겠고.. 해시맵으로 풀고 싶진 않아서 안했습니다......