알고리즘/[ Baekjoon ]

[ BOJ ][JAVA][2331] 반복수열

kim.svadoz 2021. 4. 22. 23:53
반응형

www.acmicpc.net/problem/2331

 

2331번: 반복수열

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 9488 4267 3135 44.074%

문제

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

  • 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}의 네 개의 수가 남게 된다.

입력

첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.

출력

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

예제 입력 1

57 2

예제 출력 1

4

코드

import java.io.*;
import java.util.*;
public class p2331 {
    static BufferedReader br;
    static StringTokenizer st;
    static int A, P, dp[];
    static boolean visit[];
    static List<Integer> list;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();
        list.add(A);

        while (true) {
            int temp = list.get(list.size() - 1);

            int result = 0;

            while (temp != 0) {
                result += (int) Math.pow(temp % 10, (double) P);
                temp /= 10;
            }

            if (list.contains(result)) {
                int ans = list.indexOf(result);
                System.out.println(ans);
                break;
            }

            list.add(result);
        }


    }

}
반응형