(c++)백준 2331번: 반복수열

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

2331번: 반복수열

[풀이]

dfs를 사용하여 풀었다.

수열을 구하면서 check[값]을 해당 값이 나올 때마다 +1해주다가 어떤 값이 3번 나오면 반복수열이 되었다는 뜻이므로 함수에서 빠져나온다. 

ex) 37, 58, 89, 145, 42, 20, 4, 16, 37, 58, 89, 145, 42, 20, 4, 16, 37, ... 이렇게 37이 세번 나와야 반복수열이 되었다는 것을 알 수 있다.

check값이 1인 인덱스들이 반복되는 부분을 제외했을 때 수열에 남게되는 수들이다.

 

#include <iostream>
#include <cmath>//pow
using namespace std;
#define Max 240000

int A, P;
int check[Max];//각 숫자가 몇번 나왔는지 체크

void dfs(int num) {
	check[num]++;

	//같은 부분이 한 번 반복되면 리턴
	if (check[num] == 3) {
		return;
	}

	//수열 구하기
	int next = 0;
	while (num) {
		next += pow(num % 10, P);
		num /= 10;
	}
	dfs(next);
}

void solution() {
	cin >> A >> P;
	dfs(A);
	int cnt = 0;
	for (int i = 1; i < Max; i++) {
		//한 번만 나왔던 수의 개수 세기
		if (check[i] == 1)
			cnt++;
	}
	cout << cnt << endl;
}

int main() {
	solution();
	return 0;
}