[BOJ] 2331 반복수열

DFS로 풀어야하는 문제였는데 처음에는 이게 어떻게 DFS가 되는지 고민해야 했다. 그래도 고민해서 BFS로 하면 되는구나 하고 알아내긴 했다. 

 

수가 매우커진다고 생각했기 때문에 vector를 쓰려고 했는데 vector는 또 탐색을 어떻게 진행해야하는지가 문제였다. find함수를 사용하려했는데 내가 원하는 범위안에서만 값을 찾는 방법을 알아내지 못해서 for문으로 그냥 반복해서 값을 확인해주는 코드를 작성하였다. 

 

다른사람이 작성한 코드를 보니 최대 값도 3만이 넘지 않는다고 측정하여서 범위를 한정시킬 수 있었다. 그걸 배열로 작성하여 주니 좀 더 간단하게 해결되었다. 

 

내가 작성한 코드는 if문이 많아서 별로 좋은 코드는 아닌 것 같다.

 

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

vector<int> v;
int A, P, end_num, cal_res, cnt =0;
bool start_count ;
int cal(int n){
    int sum = 0;
    int len = log10(n);
    for(int i =0 ; i< len +1 ; i++){
        sum += pow( n%10, P);
        n/=10;
    }

    return sum;
}
bool exist(int n){
    for(int i =0 ;i< v.size()-1; i++){

        if(v.at(i)==n)
            return true;
    }

    return false;
}
void DFS(int n){
//    auto it = find(v.begin(), v.end(), n);

    if (exist(n)){
        end_num = n;
        return;
    }

    cal_res = cal(n);
    v.push_back(cal_res);
    DFS(cal_res);

    if( n == end_num ){
        start_count = true;
        return;
    }
    if(start_count)
        cnt++;

}
int main() {
    cin >> A >> P;
    v.push_back(A);

    DFS(A);
    std::cout << cnt << std::endl;
    return 0;
}

 

 

 

 

2331번: 반복수열