[백준] 2331 : 반복수열 JAVA 풀이

 

그래프 카테고리에 있지만

그래프를 어떻게 적용해야 할지 모르겠어서 우선 어레이리스트로 풀어봤다.

 

1. A와 P를 입력받는다.

2. 순열을 저장할 어레이리스트를 생성한다.

3. D[1]이 되는 A를 리스트에 추가한다.

4. D[n-1]의 각 자리수를 P제곱한 합인 sum 구한다.

5-1. 4에서 구한 sum이 리스트에 이미 있다면 그 값의 인덱스를 출력하고 반복문을 종료한다.

    ( 반복수열을 제외한 수의 개수 = sum 앞에 있는 수의 개수. sum부터는 반복수열 )

5-2. 4에서 구한 sum이 아직 리스트에 없는 값이라면 리스트에 추가한다.

 

import java.io.*;
import java.util.*;
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int A = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		
		ArrayList<Integer> list = new ArrayList<>();
		
		list.add(A);
		
		while(true) {
			String str = Integer.toString(list.get(list.size()-1));
			
			int sum = 0;
			for(int j=0;j<str.length();j++) {
				sum += Math.pow(str.charAt(j)-'0', P);
			}
			
			if(!list.contains(sum)) {
				list.add(sum);
			}
			else {
				System.out.println(list.indexOf(sum));
				break;
			}
		}
	}

}

 

다른 사람들의 코드를 참고해서 다시 풀어본 코드

import java.io.*;
import java.util.*;
public class Main{
	// 이미 이전에 나온 값인지 확인하는 용도의 배열
	static int[] visit;
    // 반복수열을 제외한 수의 개수를 세는 변수
	static int cnt = 1;
	
	public static void dfs(int a, int P) {
		
        // 처음 나오는 수라면
		if(visit[a]==0) {
        	// 이 수가 몇 번째 수인지 배열에 저장함
            // 입력 예제로 예를 들면
            // visit[57] = 1;
			visit[a] = cnt;
			
            // 각 자리수의 P제곱을 계산하기 위해 문자열로 변경
			String str = Integer.toString(a);
			int sum = 0;
			for(int i=0;i<str.length();i++) {
				sum += Math.pow(str.charAt(i)-'0', P);
			}
			
            // 카운트 증가
			cnt++;
			
            // D[n-1]의 각 자리수의 P제곱의 합을 구해서 그 값으로 다시 재귀호출
            
			dfs(sum, P);
		}
        // 이미 나왔던 수라면
		else {
        	// visit[a]부터 반복되는 것이니 -1한 값을 출력하고 리턴
			System.out.println(visit[a]-1);
			return;
		}
	}
	
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int A = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		
		visit = new int[1000000];
		dfs(A,P);
		
	}
}