[백준-2331] 반복수열 - Python

 

 

 

 

문제 소개

 

 

문제

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

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

 

Code 

 

# Python code

###########################################################
import sys
import collections
import itertools
import copy

input=sys.stdin.readline
sys.setrecursionlimit(10**7)


A , P = map(int , input().split())

Dic = collections.defaultdict(int)

def NextSerial(A1,P):
	# 수열의 다음 값을 구하는 함수 
    # 10으로 나누면서 하나씩 자리수를 짤라서 P승하고 더해나간다. 
    temp_ = 0
    while A1 > 0:
        temp_ += (A1 % 10) ** P
        A1 = A1 // 10
    return temp_


while 1:
    if Dic[A]<=1:
        Dic[A] += 1
        A=NextSerial(A,P)
    else :
        break

# 매번 수열을 구해서 Dictionary에 더한다 
# 처음에 더해지면 0에서 1로 Key의 value값이 +1씩 올라간다.
# (그러기 위해 defaultdict을 썻다.)
# 추가할때 이미 나왔던 key 라면 -> value값이 이미 1이 되었을 것이고 
# 1인 value를 탐지하는 순간 루프를 끊고 dic중에서 value가 1인 것들의 수를 구한다.

result_1 = [x for x in Dic.values() if x==1]
print(len(result_1))

 

 

 

※ end