[백준 2331번] 반복수열

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

2331번: 반복수열

<문제 풀이> DFS

이문제는 dfs로 수열을 계속 구하다가 반복 횟수가 2 이상이면 종료하고 반복 횟수가 1인 수열의 개수를 세면 되는 간단한 문제입니다.

 

그런데 문제는 배열의 범위를 설정하는 것입니다.

 

문제에서 A <=9999이고 P <=5라고 했으니깐

처음 시작되는 수의 자릿수의 최대는 4자리입니다.

 

A = x1x2x3x4라고 하면

x1^5 <= 9^5 = 59049

x2^5 <= 9^5 = 59049

x3^5 <= 9^5 = 59049

x4^5 <= 9^5 = 59049

 

따라서 

x1^5 + x2^5 + x3^5 +x4^5 <= 236196 

 

위를 통해서 A로 만들 수 있는 다음 수는 아무리 커도 6자리를 넘지 못합니다.

 

그러면 만약에 6자리가 모두 9로 이루어졌다고 가정하고 다시 계산해보겠습니다.

 

A = x1x2x3x4x5x6라고 하면

x1^5 <= 9^5 = 59049

x2^5 <= 9^5 = 59049

x3^5 <= 9^5 = 59049

x4^5 <= 9^5 = 59049

x5^5 <= 9^5 = 59049

x6^5 <= 9^5 = 59049

 

따라서

x1^5 + x2^5 + x3^5 +x4^5  + x5^5 + x6^5 <= 354294

 

위를 통해서 6자리로 최대 6자리까지만 만들 수 있으니깐, 수의 최대 자릿수는 6자리를 넘지 못한다는 걸 알 수 있습니다.

 

 

 

 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
int arr[1000000];
 
int a, p;
 
int pow(int x, int n) {
    int temp = x;
    for (int i = 0; i < n - 1; i++) {
        x *= temp;
    }
    return x;
}
 
void dfs(int a) {
    int res = 0;
    while (a) {
        int r = a % 10;
        res += pow(r, p);
        a = a / 10;
    }
    if (arr[res] < 2) {
        arr[res]++;
        dfs(res);
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> a >> p;
    arr[a]++;
    dfs(a);
    int cnt = 0;
    for (int i = 1; i <= 1000000; i++) {
        if (arr[i] == 1)cnt++;
    }
    cout << cnt;
 
    return 0;
}