백준 반복 순열 2331

2020-10-22

1. 백준 반복 순열 2331 문제

1.1. 문제

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

D[1] = A
D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합
예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5²⁺⁷2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

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

1.2. 입력

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

1.3. 출력

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

1.4. 예제 입력 1

57 2

1.5. 예제 출력 1

1.1. 컴퓨팅적 사고

이번 반복순열 문제는 중복되는 구간을 제외한 나머지영역의 개수를 구하는 문제입니다.
처음에 접근시에 인접리스트로 문제를 풀이하였었는데 9%에서 런타임에러로 계속 터지는 상황이 발생하여 처음부터 로직을 구현하게 되었습니다.
생각한 결과로 단순히 DFS로 중복이 cnt값을 1~1,000,000까지 값을 진행하다가 순열의 값을 인덱스로 한 값을 cnt값으로 변경하면서 진행하였습니다.

알고리즘 풀이

예를 들어, 수열 D는 {57, 74(=5²⁺⁷2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …}식으로 진행됩니다. 이때 37부터 값이 반복되고 있는 상황을 알 수 있습니다. check[37]은 이미 5라는 값을 가지고 있겠지요?

check[57] = 1 check[74] = 2 check[65] = 3 check[61] = 4 check[37] = 5
의 형태로 저장되는 상황일 것입니다. 따라서 반복되는 두번째시점의 37의 구간에서 37이 가지고 있는 값-1을 반환하게 된다면 중복이 나오기전의 시점의 개수를 찾아낼 수 있습니다.

아래는 DFS함수 코드의 일부를 가져왔습니다.

public static int dfs(int a, int p, int cnt) {
    if (check[a] != 0) {
        return check[a]-1;
    }
    check[a] = cnt;
    int b = getNextNumber(a, p);
    return dfs(b, p, cnt+1);
}

37로 예를 들어 check[37]은 이미 할당되어있는 값이므로 중복되는 시점입니다. 따라서 현재 값이 할당된 cnt값의 -1은 중복되지 않은 값의 개수를 알 수 있습니다.

나머지는 한자리 숫자의 합을 구해주는 getNextNumber()함수로 계속해서 값을 진행하게 하였습니다. 그리고 dfs를 호출해주면서 이미 값을 가지고 있으면 해당값을 리턴하여 종료하게 하였습니다.

1.2. 소스코드

import java.util.*;
public class 반복수열2331 {
    public static int[] check = new int[1000000];
    public static int getNextNumber(int a, int p) {
        int ans = 0;
        while (a > 0) {
            ans += Math.pow(a%10, p);
            a /= 10;
        }
        return ans;
    }
    public static int dfs(int a, int p, int cnt) {
        // 예: check[37]은 이미 할당되어있는 값이므로 중복되는 시점이다. 따라서 현재 값이 할당된 cnt값의 -1은 중복되지 않은 값의 개수를 알 수 있다.
        if (check[a] != 0) {
            return check[a]-1;
        }
        check[a] = cnt;
        int b = getNextNumber(a, p);
        return dfs(b, p, cnt+1);
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int p = sc.nextInt();
        System.out.println(dfs(a, p, 1));
    }
}

AlgorithmBOJ