2331-반복수열

2331번: 반복수열

재귀함수를 사용하여 DFS를 구현하였다

1. dfs에서 숫자를 받아서 배열 저장 후 다음 순서 숫자를 구한다 

2. 만약 현재 숫자와 다음숫자가 (같은순서로) 이미 배열에 존재하는 숫자의 순서라면

3. dfs를 빠져나간다

 

package com.exam;

import java.util.ArrayList;
import java.util.Scanner;

public class B2331 {
    static int A,P;
    static ArrayList<Integer> sumArr = new ArrayList<>();
    static boolean finish;

    static void dfs(int a){
        sumArr.add(a);
        int sumA = 0;
        String[] str = String.valueOf(a).split("");
        for (String s : str) {
            sumA += Math.pow(Integer.parseInt(s), P);
        }
        if(sumArr.size()>1) {
            for (int i = 0; i < sumArr.size()-1; i++) {
                if (sumArr.get(i) == a && sumArr.get(i + 1) == sumA) {
                    sumArr.subList(i,sumArr.size()).clear();
                    System.out.println(sumArr.size());
                    finish = true;
                }
            }
        }
        if(!finish) dfs(sumA);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        A = sc.nextInt();
        P = sc.nextInt();
        dfs(A);
    }
}