[BOJ] 백준 2331번 : 반복수열 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/2331

2331번: 반복수열

문제

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 {57, 74, 65, 61}의 네 개의 수가 남게 된다.

 

풀이

간단한 수학적 지식과 자료구조의 contains method를 이용하면 쉽게 해결할 수 있는 문제였습니다. 위에 예제에서 D = {57, 74, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, 58,...}으로 주어진다고 하였습니다. 즉, {37, 58, 89, 145, 42, 20, 4, 16}은 반복되기때문에 반복되지 않는 수열 {57, 74, 65, 61}의 개수인 4개가 정답입니다.

따라서, ArrayList에 각 수를 P만큼 제곱한 값을 계속 추가하면서 어떤 수가 이미 ArrayList에 포함되어있다면, 그 수의 인덱스를 반환하면 됩니다.

위 예제에서는 37이 반복되는 수열의 시작점이기때문에 인덱스 4를 반환하면, 우리가 구하려는 수열의 사이즈를 구한 것이라고 판단할 수 있습니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
 
        List<Integer> list = new ArrayList<>();
        list.add(A);
 
        while (true) {
            int temp = list.get(list.size() - 1);
 
            int result = 0;
            // 어떤 수의 각 자리에 대해 P제곱만큼하여 각 자리를 더한 값을 구함.
            while (temp != 0) {
                result += (int) Math.pow(temp % 10, (double) P);
                temp /= 10;
            }
 
            // result가 이미 list에 포함되어있다면,
            // 그 result가 가리키는 인덱스를 반환.
            if (list.contains(result)) {
                int ans = list.indexOf(result);
                bw.write(ans + "\n");
                break;
            }
 
            list.add(result);
        }
 
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.