백준 2331번 반복수열

문제 링크입니다: https://www.acmicpc.net/problem/2331

간단한 DFS(Depth First Search) 알고리즘 문제였습니다.

알고리즘은 아래와 같습니다.

1. A=9999이고 P=5일 때 연산 결과가 최대가 되는데 이 때 값이 30만보다 작으므로 visited 배열 크기를 30만으로 잡았습니다.

2. A부터 DFS를 시작하는데 해당 숫자가 방문될 때마다 visited 배열의 해당 인덱스를 1 증가시킵니다.

3. visited 배열의 해당 인덱스 값이 3이 된다면 반복 수열이 두번째 반복하는 시점이므로 재귀 함수를 탈출합니다.

4. 이후 visited 배열을 전부 방문하면서 한번만 등장한 숫자들의 갯수를 파악하고 결과를 출력합니다.

#include <iostream>

#include <cmath>

#include <cstring>

using namespace std;

 

const int MAX = 300000 + 1;

 

int P;

int visited[MAX];

 

void DFS(int num)

{

        visited[num]++;

        //반복구간이 한번 반복되었다는 것을 의미

        if (visited[num] == 3)

                 return;

        int sum = 0;

        while (num)

        {

                 sum += (int)pow((num % 10), P);

                 num /= 10;

        }

        DFS(sum);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int A;

        cin >> A >> P;

 

        DFS(A);

        int result = 0;

        //한번만 등장한 숫자들이 반복구간에 속하지 않은 숫자들

        for (int i = 0; i < MAX; i++)

                 if (visited[i] == 1)

                         result++;

 

        cout << result << "\n";

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~