6장 그래프 - (3) 그래프 탐색 문제 4 - 반복수열(2331번)

1. 반복수열(2331번)

(내 소스)

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

vector<int> d;

bool check[236197];

int p;

int next(int a) {

int ans = 0;

while (a > 0) {

ans += pow(a % 10, p);

a /= 10;

}

  return ans;

}

// 수열을 구해나가다가, 반복된 값이 나오면 해당 값을 return

int go(int x) {

if (check[x] == true) {

return x;

}

check[x] = true;

d.push_back(x);

go(next(x));

}

int main(void) {

int a;

cin >> a >> p;

int result = go(a);

int cnt = 0;

for (auto &temp : d) {

if (temp == result) {

break;

}

cnt++;

}

cout << cnt << endl;

return 0;

}

(정답 소스)

#include <iostream>

#include <cmath>

using namespace std;

int check[1000000];

int p;

int next(int a){

int ans = 0;

while(a>0){

ans+=pow(a%10,p);

a/=10;

}

return ans;

}

int length(int a, int cnt){

if(check[a]!=0){

return check[a]-1;

}

check[a] = cnt;

int b = next(a);

return length(b, cnt+1);

}

int main(void){

int a;

cin >> a >> p;

cout << length(a,1) << '\n';

return 0;

}