백준 2331번 - 반복수열

2331번: 반복 수열 (acmicpc.net)

2331번: 반복수열

---

반복 수열성공

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

256 MB

8924

3975

2906

43.601%

문제

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

• 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)가 주어진다.

출력

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

 

---

[ 문제 설명 ]

 

예제처럼 57, 2 가 주어지면 각각의 자릿수를 2 제곱해서 나온 수가 다음 수열인 수열 중 반복 수열이 안 되는 수열의 개수를 구하는 문제.

57 -> 5 ** 2 + 7 ** 2 = 74 -> 74(다음 수열) -> 7 ** 2 + 4 ** 2 = 65 ->.... 이런 식

 

그림으로 설명하겠다.

 

그림 1 - 반복 수열 설명

 

그림을 보시고 코드를 보시면 이해가 될겄임.

 

---

[ 코드 ]

# 제곱해주는 역할
def Daum(N, M):
    n = str(N)
    res = 0
    for i in n:
        res += pow(int(i), M)
    return res


def DFS(N, M, iteration, check):
    # 이미 한 번 계산 됬다면, 이제 반복된다고 판단
    if check[N] != 0:
        # print(N)
        return check[N] - 1

    check[N] = iteration
    # print(N)
    daum = Daum(N, M)
    iteration += 1
    return DFS(daum, M, iteration, check)


import sys

N, M = map(int, sys.stdin.readline().split())
check = [0] * 236197  # 9 ** 5 + 9 ** 5 + 9 ** 5 + 9 ** 5 최대 인덱스의 값이기 때문
iteration = 1

print(DFS(N, M, iteration, check))

 

 

그림을 보시고, 코드를 음미해보시면 이해가 되실 것.

 

---

후기

 

매우 간단한 문제지만. 신기한 문제

수학자들은 제곱을 한 값이 반복될 거라는 걸 어떻게 안 걸까?

생각이 된다.