[ 백준 / C++ ] 2331 : 반복수열

[ 문제 ]

 

2331번: 반복수열

 

[ 접근방법 ]

 

값의 중복 여부는 map 자료구조를 활용하여 판단하였다.

 

map은 key-value 쌍으로 데이터를 저장하는 자료구조로, key의 중복을 허용하지 않는다.

또한, 내부적으로 key가 정렬된 상태로 유지되므로 삽입, 삭제, 검색 연산을 O(log n) 만에 수행한다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

int cal(int x, int y){
    int res = 0;

    while(x){
        res += (int)pow(x % 10, y);
        x /= 10;
    }

    return res;
}

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

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

    vector<int> d;
    map<int, int> chk;

    d.push_back(a);
    chk[a] = d.size();

    while(1){
        int cnt = cal(d.back(), p);
        if(chk.find(cnt) == chk.end()){
            d.push_back(cnt);
            chk[cnt] = d.size();
        }
        else{
            cout << chk[cnt] - 1;
            break;
        }
    }

    return 0;
}