[구현] 2331번 - 반복수열

[백준] 2331번 - 반복수열

풀이 시간: 20분 이내

 

1) 문제 해결 아이디어

이 문제는 설명에 나와있는대로 구현을 하면 되는 문제였다. 아이디어만 쉽게 떠올리면 금방해결되는 문제!

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

위와 같은 연산을 반복했을 때 만들어지는 수열에서 반복되는 부분을 제외한 수들의 개수를 구하는 것이다.

반복이 시작되는 지점의 인덱스를 찾아 그 인덱스를 출력시켜주면 된다.

여기서 중요한 점은 연산을 해서 현재 만들어낸 값(num)이 수열(d)에 있다는 조건을 최초로 만족할 때 그 값(num)이 반복이 시작되는 값이 된다는 것이다. 그러므로 반복이 시작되는 값의 인덱스(start)를 찾으면 정답이다.

 

2) 소스코드

a, p = map(int, input().split())  # 첫번째 수, 제곱
d = [a]  # 반복 수열
i = 0
start = 0  # 반복 시작 지점
while True:
  num = 0 
  # 각 자리숫자를 P번 곱한 수들의 합
  for n in str(d[i]) :
    num += int(n)**p
  # 현재 숫자가 d에 이미 있는 숫자라면(탈출 조건)
  if num in d:
    start = d.index(num)
    break
  # 현재 숫자가 d에 없다면 리스트에 넣고 인덱스 변경
  d.append(num)
  i += 1

print(start)