[BOJ]2331. 반복 수열

문제:

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

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

출력:

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

풀이방법:

 DFS를 사용해서 풀어야 하는 문제이다. check라는 배열을 250000이라고 설정하고(최대 나올 수 있는 값은 9^5+9^5+9^5+9^5 이기 때문이다.) dfs로 하나씩 들어가면서 해당하는 값에 count를 할당한다. 이렇게 계속해서 값을 구하다가 check가 0이 아닌 값을 만난다면 그 값부터는 반복된다는 뜻이므로 그 check의 count에 1을 뺀 값이 정답이 되게 된다.

 이 문제로 예시를 들면 check[57]에 count를 1을 할당. ->check[74]에 2를 할당 -> check[65]에 3을 할당 -> check[61]에 4를 할당 -> check[37]에 5를 할당 -> check[58]에 6을 할당 -> check[89]에 7을 할당 -> check[145]에 8을 할당 -> check[42]에 9를 할당 -> check[20]에 10을 할당 -> check[4]에 11을 할당 -> check[16]에 12를 할당 -> check[37]에는 이미 5가 할당되어 있음. 따라서 57, 74, 65, 61만 남아야 하므로 답은 5-1인 4가 된다.

def next(A,P):
    a=str(A)
    answer=0
    for i in a:
        answer+=pow(int(i),P)
    return answer
 
def dfs(A,P,count,check):
    if check[A]!=0:
        return check[A]-1
    check[A]=count
    b= next(A,P)
    count+=1
    return dfs(b,P,count,check)
 
 
check=[0]*250000
A, P =map(int,input().split())
count=1
print(dfs(A,P,count,check))

문제링크:

https://www.acmicpc.net/problem/2331