[백준] 2331번 반복수열

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

이 문제를 보자 마자 dfs 를 사용하여 반복되는 값이 나오면 dfs를 빠져나와 그 전 까지의 수의 개수를 구할 수 있을 거라 생각하였다.

리스트로 구현을 해보고 해시로도 구현을 해보았지만 dfs를 사용하지 않고도 구현할 수 있는 방법이 있었다.

나의 첫 번째 풀이

1. 배열의 범위 설정. 9^5 + 9^5 + 9^5 + 9^5 + 9^5 = 약 250000개를 미리 설정한다. 배열의 범위를 미리 정해놔야 D[i] = n 형태로 배열의 해당 인덱스의 값을 바꿔줄 수 있기 때문이다.

2. 반복문을 돌려 다음 D[i+1] 에 들어갈 value를 구하고 그 값이 D 배열에 있다면 break, 없다면 D[i+1] = value로 교체한다.

D 배열에 num 값이 있으면 해당 값부터 반복되는 값이 시작되므로 그 값의 index를 찾아 -1을 해준 값이 정답이다. (-1을 해주는 이유는 D[1] 부터 값을 넣어주었기 때문이다.)

import sys

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

D = [0]*250000
D[1] = A
index = 1

while True:
    num = 0
    index += 1

    for n in str(D[index-1]):
        num += (int(n)**P)

    if num in D:
        print(D.index(num) - 1)
        break
    else:
        D[index] = num

위와 비슷한 방식으로 이렇게도 풀 수 있다.

import sys

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

def repeat(n):
    num_list = [n]
    while(True):
        temp = 0
        for i in str(num_list[len(num_list)-1]):
            temp += int(i)**P
        if temp in num_list:
            break
        else:
            num_list.append(temp)

    return num_list.index(temp)

print(repeat(A))

나의 두 번째 풀이

dfs를 사용하여서 풀어도 보았다.

1. D 배열에 똑같이 250000개를 초기화 해준다.
2. 재귀함수를 구현하여 D[57] = 1, D[74] = 2, D[65] = 3 처럼 D[A] = cnt++ 형식으로 만들어 준다.
3. 탈출식은 D[A] != 0 인 경우, 즉, 한번이라도 방문 했던(cnt를 셌던) index가 나오면 해당 cnt값에 -1을 하고 dfs()를 빠져나온다.

D[A] = 1 로 설정하는 이유는, 만약 반복 수열이 첫 번째 값부터 시작 된다면 정답은 0이기 때문이다.

import sys
sys.setrecursionlimit(10000)

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

D = [0]*250000
D[A] = 1
def dfs(A, cnt):
    num = 0
    for n in str(A):
        num += (int(n)**P)

    if D[num] != 0:
        print(D[num]-1)
        return
    else:
        cnt += 1
        D[num] = cnt
        dfs(num, cnt)

dfs(A, D[A])