백준 2331번: 반복수열

• 사용언어 python

중복을 분기로하여 계속 중복 체크를 해주어야하는 문제이므로 DFS를 사용하게 되었다.

1. 문제

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

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)가 주어진다.
- 출력 : 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

2. 코드

# 수열의 수 계산
def cal_sequence(a, p):
    answer = 0
    for i in str(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
    next = cal_sequence(a, p)
    count += 1
    
    # 중복이 생길 때 까지 탐색
    return dfs(next, p, count, check)

def solution():
    # 각 index는 수열의 수를 뜻함
    check = [0]*250000  # 최댓값 4*9^5
    
    # 첫수, 제곱 횟수
    a, p = map(int, input().split())
    count = 1   # 나온 수열의 개수
    print(dfs(a, p, count, check))

if __name__== "__main__":
    solution()

3. 풀이

1. 풀이
   1). cal_sequence를 통해 계산된 수 = answer
   2). 현재 까지 중복 없이 나온 수열의 개수 = count
   3). check[answer] = count
   - 만약 중복된 수가 나온다면 check 리스트에서의 그 위치는 이미 count 로 채워져 있을 것이다.
   - count != 0 이면 중복 된 것이므로 재귀를 멈추게 된다.

2. DFS 사용

• 중복이 나오는 것을 분기로 하여 그때 까지 탐색 수행