백준 알고리즘 - 반복수열 (2331) [Python]

 

 

 문제

 

www.acmicpc.net/problem/2331

2331번: 반복수열

 

 

 

 

 

 

 

 문제 상황

 

- 반복적인 연산을 통해 수열을 만들고 겹치는 부분이 발생했을 때 겹치지 않는 부분의 길이를 구하는 문제

 

 

 

 

 

 

 해결 전략

 

- 연산을 반복하면서 조건을 설정해 해당 조건이 아니면 수열에 추가하고, 맞으면 반복을 탈출하며 그 반복 요소의 위치를 찾는다.

 

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
A, P = input().split()
D = [A]
while True:
    A = D[-1]
    total = 0
    for i in range(len(A)):
        total += (int(A[i])**int(P)) # 각자리를 P제곱하여 더해준다
    if str(total) not in D:
        D.append(str(total))
    else : 
        print(D.index(str(total)))
        break

 

 

 

 

 

 

 

 

 해설

 

- 리스트의 마지막 요소를 연산에 활용하여 조건을 찾고, 요소에 이미 존재하는지 여부를 판단한다. 연산에 소요되는 시간이 O(N)이고, 리스트에 요소가 존재하는지 확인하는데 소요되는 시간이 O(M)이 된다. 이것이 while문으로 감싸져 있어 약 O(N^2)의 시간으로 예상된다.

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 처음에 반복 요소가 발견되면 그 때까지 나온 요소들의 개수를 구하였는데 문제의 조건은 반복되지 않는 부분의 길이를 구하는 것이므로 그 요소의 위치를 찾아 출력하면 된다.