BOJ 2331번 반복 수열

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/2331/2331/%EC%86%8C%EC%8A%A4.cpp

 

반복수열의 범위를 먼저 확인해보는게 중요하다.

한자리 숫자가 가질 수 있는 값 중 가장 큰 값은 9이고 9 의 5 제곱은 5만쯤 된다.

D[1] 이 최대 9999 이니 *4 를 하면 20만이고 (사실 정확히 계산해보면 236196)

길이가 어떻게 길어질지 계산해보기 귀찮아서 어림잡아 100만을 줬는데 반복 수열을 확인하는데는 

충분한 범위일 것 같다.

 

이후부터는 문제가 요구하는대로 수열을 찾아서 첫 위치에 대한 카운트를 해주면 된다.

 

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> v;
bool arr[1000001], check = 1;
 
int main() {
    int A, P, index = 0;
    cin >> A >> P;
    v.push_back(A);
    arr[A] = 1;
 
    int total;
    while (check) {
        total = 0;
        int temp = v[index];
        while (temp) {
            int num = temp % 10;
            int cnt = P;
            int test = 1;
            while (cnt--) test *= num;
            total += test;
            temp /= 10;
        }
        if (arr[total]) {
            check = 0;
        }
        else arr[total] = 1, v.push_back(total), index++;
    }
 
    int cnt = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == total) break;
        cnt++;
    }
 
    cout << cnt;
    return 0;
}