[백준] 2331 반복순열 (C++)

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

2331번: 반복수열

 

문제 설명

---

풀이 과정

• 나의 풀이

① 문제 바라보기

  최근에 dfs & bfs 문제만 유형별로 골라서 풀고 있는중이라 문제 유형을 알고 푸니 쉽게 접근이 가능했다.

  주어진 A, P값에 따라 반복순열이 다르게 나온다. 예제 1의 경우 57 -> 74 -> 65 -> 61 -> ... -> 37 , 58 -> 89 -> ... -> 37 -> 58 로 순열이 나타난다. n번쨰 값이 n-1번째 값으로부터 파생된다는 점에서 일종의 방향성을 발견할 수 있었다! 

 

② 아이디어 열기

  문제에서 구하고자 하는 값은 무한으로 반복되는 순열 전까지의 순열값의 순서이다. 따라서 dfs로 탐색하며 파생되는 값의 인덱스에 1을 더하고, 인덱스값이 2라면 탐색을 멈추도록 하였다.

#include <iostream>
#include <cmath>

#define MAX 295246           // 파생되는 숫자의 최대값은 295245이기에  

int visited[MAX] = {0,};     // 전부 0으로 초기화
int P;                       

void dfs(int x) {            // dfs 함수 
    
    if (visited[x] == 2) return ;       // 반복순열의 시작이라면 탐색 종료

    visited[x] += 1;                    

    int result = 0;                      
    while (x)
    {
        result += (int)pow( (x%10),P );
        x /= 10;
    }

    dfs(result);
}

int main(void) {
    int A;
    std::cin >> A >> P;

    dfs(A);
    int result = 0;
    
    for (int i = 0; i < MAX; i++) {
        if (visited[i] == 1) result++;
    }
    
    std::cout << result << "\n";

    return 0;
}