BOJ 2331 - 반복수열

문제

백준 온라인 저지 - 2331번

풀이 과정

규칙에 따라 생성되는 숫자들을 모두 탐색하며 최종적으로 반복되는 수열을 제외한 나머지 숫자들의 개수를 구하는 문제입니다.

이를 위해 DFS 탐색을 수행하며 각 숫자들을 처음 방문, 두번째 방문, 세번째 방문 이렇게 세 종류로 구분해줍니다.

첫번째 방문의 경우는 문제가 없지만 두번째 방문했을때는 해당 숫자가 중복되어 나타난다는 의미이므로 방문횟수를 증기시킨 후 다음 탐색을 수행합니다.

이때 가장 처음 세번째 방문되는 숫자가 나타나는 경우 이후의 숫자들은 또다시 겹치게 되므로 탐색을 계속 수행할 필요없이 바로 종료해주면 됩니다.

코드

import sys

sys.setrecursionlimit(10**6)

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


def dfs(here, log):
    if log[here] >= 2:
        return

    log[here] += 1

    new_value = 0
    for d in str(here):
        new_value += int(d) ** P

    if new_value not in log:
        log[new_value] = 0
    dfs(new_value, log)


def solution():
    log = {A: 0}
    dfs(A, log)

    # 1번만 발견된거 카운트
    ans = 0
    for val in log.values():
        if val == 1:
            ans += 1
    return ans


print(solution())