<구현> 2331번 반복 수열 with 파이썬

 

문제

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

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

출력

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

정답비율

43.924%

 

def multiply_p(x) :
    x = int(x) ** p
    return x

a, p = map(int, input().split())
lst = [a]
i = 0

while True :
    i += 1
    num = sum(map(multiply_p, str(lst[i-1])))
    if num in lst :
        break
    lst.append(num)

print(lst.index(num))

 

 - 각 자리의 숫자를 P번 곱한 수들의 합을 어떻게 배열에 잘넣을까를 오래 고민했다. map함수에 int나 str 외에는 처음으로 다른 함수를 넣어보았는데 잘 작동해서 다행이다. map 함수를 이용해서 i-1번째 배열요소를 문자열로 만들어서 각자리의 숫자를 튜플형태로 받게하였고, 각각의 숫자에 multiply_p 함수를 적용하도록 했다. 그렇게하면 함수가 정의된 숫자들(p제곱된 숫자들)이 튜플형태가 될 것이며 이를 sum으로 모두 더하였다.

 

 - 구한 숫자를 리스트에 추가해주면 문제에 나온리스트가 완성된다. 문제에 나온 입력대로 57 2를 입력하면 다음과 같은 배열이 만들어진다.

 [57, 74, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, 58, 89, 145, 42 ...]

 

 - 한번 같은 숫자가 나오게 되면 반드시 그 뒤의 숫자들은 반복된다. 왜냐하면 각 자릿수를 이용하여 숫자를 구하므로 동일한 과정이 반복될 것이다.

 

 - 따라서 무한루프를 생성하고 num을 구할 때마다 리스트에 같은 숫자가 있는지 체크하고, 있다면 반복문을 종료한다.

 

 - 같은 숫자의 인덱스를 찾으면 그것이 곧 답이된다.

 

---

 

참고

 

2331번: 반복수열