[Silver IV] 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)가 주어진다.

출력

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

예제 입력 1

57 2

예제 출력 1

4

---

# 풀이 방법

수열 > dfs 접근하려고 했으나 굳이 dfs로 할 필요가 있나 하는 생각이 들었다.. 더 간단히 할 수 있을 것 같은데

 

이 경우에는 graph를 전체 다 입력 받고 하나씩 도는게 아니라 노드를 추가하면서 더 갈지말지 결정하는 방법이었다.

1. 다음 노드 숫자 구하기

2. 다음 노드 숫자가 이전에 있던 숫자인지 구하기

2-1. 이전에 있던 숫자라면, 인덱스(남게 되는 수) 출력

2-2.  이전에 없던 숫자라면, 배열에 추가하고 계속 위의 과정 반복

---

# 코드

import sys
import math

sys.stdin = open("input.txt", "r")

A, P = map(int, sys.stdin.readline().split())
perm = [A]

def next(A):
    next_A = 0
    while A != 0:
        next_A += math.pow(A%10, P)
        A //= 10
    return next_A

while True:
    next_A = next(A)
    if next_A in perm:
        break
    perm.append(next_A)
    A = next_A
print(perm.index(next_A))

 

---

# 참고

index함수를 쓰면 더 간단하다 아래는 복잡 ver

from collections import deque
import math
import sys
sys.stdin = open("input.txt","r")
a, p = map(int,sys.stdin.readline().split())
perm = []
perm.append(a)

def return_next(curr,p):
    next = 0
    while curr != 0:
        next += math.pow(curr%10,p)
        curr = curr // 10
    
    return int(next)

curr = a
while True:
    next = return_next(curr,p)
    if next not in perm:
        perm.append(next)
        curr = next
    else:
        for i in range(len(perm)):
            if perm[i] == next:
                break
        break

print(i)