[재귀] 백준 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. 해당 숫자(d)를 String으로 변환하여 charAt 메서드를 사용해서 인덱스별로 숫자 자릿수를 가져온다

2. 숫자 자릿수에 p 제곱을 하여 sum(init = 0)에 더한다.

3. String length만큼 1~2번을 반복한다.

4. 해당 sum을 list에 추가하고, 재귀를 돌린다

5. 재귀를 돌릴 때 d가 list에 포함되면 탈출한다. 이때 해당 숫자의 list 인덱스 위치를 반환하여 정답을 구한다.

---

코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static int num = 0;
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String input = bf.readLine();
        String[] inputs = input.split(" ");
        int d = Integer.parseInt(inputs[0]);
        int p = Integer.parseInt(inputs[1]);
        ArrayList list = new ArrayList<Integer>();
        dfs(d, p, list);
        System.out.print(num);
    }
    public static void dfs(int d, int p, List<Integer> list){
        if(list.contains(d)){
            num = list.indexOf(d);
            return;
        }
        list.add(d);
        int sum = 0;
        String ds = Integer.toString(d);
        for(int i = 0; i < ds.length(); i++){
            int n = Character.getNumericValue(ds.charAt(i));
            sum += Math.pow(n, p);
        }
        d = sum;
        dfs(d, p, list);
    }
}