[백준 - 2331][Silver 4] - 반복수열 (JAVA)

문제 링크

---

https://www.acmicpc.net/problem/2331

 

문제

---

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

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

예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=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)가 주어진다.

 

출력

---

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

 

구현으로 풀릴까??

---

우선 가장 쉬운 방법인 구현을 생각해보자. 

각 자리를 P번 곱한 수의 합을 더하기 위해선 숫자를 문자열화 시켜서 각 자리수를 인덱스를 이용해서 접근한 뒤 P제곱을 하면 쉽게 D[n]을 구할 수 있을 것 같다.

위의 나온 숫자를 저장한 뒤 이후에 다시 등장한다면 해당 숫자는 반복되는 부분의 수이다.

하지만 우리는 반복되는 수를 모두 제거해야된다. 그러므로 2번째가 아니라 3번째 등장할 때까지 반복을 진행한 뒤 1번만 등장한 수의 개수를 구하면 될 것이다!

위의 방법의 시간복잡도를 계산하면 다음과 같다.

 

O(N)
= (가능한 경우의 수 첫번째) + (가능한 경우의 수 두번째)
= N + N
≒ N

 

 우선 시간복잡도 계산을 위해 N의 최대값을 알아야한다. D[n]은 D[n-1] 모든 자리수의 크기를 더하는 것이므로 각 자리수가 가장 큰 경우를 생각하면 된다. 이때 입력값이 최대 9999이므로 9999부터 시작하면 수의 배열은 9,999 -> 236,196 ->  67,587 -> 61,500 ... 이 되므로 나올 수 있는 가장 큰 수는 236,196이다. 그러므로 N의 최대값은 236,196이다.

시간복잡도는 N이므로 제한된 시간인 2초의 예상 연산 횟수인 2억보다는 작기 위해서 N이 2억 미만이면 위의 방식으로 가능한데 N은 최대 236,196이므로 위의 구현 방식으로 문제를 해결할 수 있다!

 

문제 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int A = Integer.parseInt(input[0]);
        int P = Integer.parseInt(input[1]);
        long num = A;

        Map<Long,Integer> map = new HashMap<>();	//key: d[i], value : 나온 횟수

        while(true){
            map.put(num,map.getOrDefault(num,0)+1);

            //2번 이상 나왔을 경우(순환이 모두 끝나고 3번째 순환이 시작되는 경우)
            if(map.get(num) > 2){
                break;
            }

            //숫자를 문자열화 시키고 인덱스로 접근해 d[n]을 구하는 부분
            String numStr = String.valueOf(num);
            long next = 0;

            for(int  i=0;i<numStr.length();i++) {
                next += (long) Math.pow(Character.getNumericValue(numStr.charAt(i)), P);
            }

            num = next;
        }

        int sum = 0;
  
        //한번만 등장한 값의 개수를 구한다.
        for(Long key : map.keySet()){
            if(map.get(key) > 1){
                continue;
            }
            sum++;
        }

        System.out.println(sum);
    }
}

 

 

실행 결과

---

 

 

제한시간인 2초 안에 문제가 해결되었다!

 

팁

---

• N을 모르겠으면 가장 큰 경우의 수가 나올 수 있도록 주어진 조건을 대로 값을 구해보자.