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

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

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int a, p;
    cin >> a >> p;

    vector<int> ans;
    ans.push_back(a);

    int idx = -1;
    int cur = a;

    while (1) {
        int nxt = 0;

        while (cur > 0) {
            int rem = cur % 10;
            int tmp = 1;
            for (int i = 0; i < p; i++) tmp *= rem;
            nxt += tmp;
            cur /= 10;
        }
        
        int ansn = ans.size();
        for (int i = 0; i < ansn; i++) {
            if (ans[i] == nxt) {
                idx = i;
                break;
            }
        }

        if (idx != -1) break;

        ans.push_back(nxt);
        cur = nxt;
    }

    cout << idx << '\n';
}

단순히 수열을 계속 저장하면서 구해가면서, 이번에 새로 계산된 값이 이전에 나온 적이 있는지 선형적으로 체크하고, 만약 있다면 그 인덱스를 저장해서 출력하도록 했다. 왜냐하면 이전에 나온 적이 있다면 그 순간부터 무조건 반복되기 때문이다. (AC)