[백준] # 2331. 반복수열 (파이썬)

문제 링크

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

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

 

출력

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

 

IDEA

배열 d에 다음 값을 계산한 후 그 값이 이미 배열에 있으면, 그 값의 처음 인덱스가 답이다.

 

CODE

# 2331. 반복수열 - 실버 4
n, p = map(int,input().split())
d = [n]
i = 0
def nextNum(k):
    a = str(k)
    result = 0
    for i in a:
        result += pow(int(i),p)
    return result
while True:
    next = nextNum(d[i])
    # next가 d 안에 있다면, 반복되지 않은 수의 개수는 next값이 처음 나온 index와 같다.
    if next in d:
        print(d.index(next))
        break
    d.append(next)
    i += 1

 

사용 알고리즘

구현

 

풀이 평

파이썬의 배열의 index 라이브러리 덕분에 간단하게 풀었다.