출처 BOJ

반복수열

문제

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합
  예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이 때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 {57, 74, 65, 61}의 네 개의 수가 남게 된다.

입력

첫째 줄에 A(1≤A≤9999), P(1≤P≤5)가 주어진다.

출력

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

예제

풀이

구하려는 값 = 반복되는 수열을 제외하면 몇개가 남는가 = 다시 방문 전까지 지나친 개수가 몇개인가
→ 지나온 값들의 연결은 중요하지 않음, 해당 값의 cnt만 기록

코드

code

#include<cstdio>
#include<vector>
#include<cmath>
#define MAX 1000000

using namespace std;

int P;
int cnt[MAX];

int calc(int num){
	int value=0;
	do{
		value += pow(num%10,P);
		num = num/10;
	}while(num != 0);

	return value;
}

void find(int Num){
	int next = calc(Num);
	if(cnt[next] == 0){
		cnt[next] = cnt[Num] +1;
		find(next);
	}
	else
		printf("%d\n",cnt[next]-1);
}

int main(){
	int Num;
	scanf("%d%d",&Num,&P);

	cnt[Num] = 1;
	find(Num);
}

복잡도

$O(N)$
N(반복 값 나올때 까지의 갯수)의 정확한 값은 모르지만 1번씩만 지나가면서 해결 가능