BOJ 2331 반복수열

문제출처 : https://www.acmicpc.net/problem/2331

1. 문제요약

- D[1] = A

  D[n] = D[n-1]의 각 자릿수의 숫자를 P번 곱한 수들의 합

- A = 57, P = 2일 때,

  {57, 74(5^2 + 7^2 = 25 + 49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, ...}

  여기서 {57, 74, 65, 61}을 제외한 숫자는  반복된다.

- 1 <= A <= 1,000

- 1 <= P <= 5

- 반복되지 않는 숫자의 개수는?

2. 접근방법

- 두 가지를 생각해 봤는데

1) V[num] = cnt

2) V[cnt] = num

- 1) 방법은 해당 특정 숫자가 몇번째 인지 저장해서 한번 방문했던 숫자를 재 방문하면 해당 cnt를 리턴

      num이 얼마나 커질지 모름....

- 2) 방법은 cnt에 num을 가지고 있음

      배열의 크기는 최대 1000을 넘지 않지만

      해당 숫자가 이전에 있었는지를 연산 후에 매번 확인해줘야함.

3. 시간복잡도

- 1)은 O(N) : 1,000

- 2)는 O(N^2) : 1,000,000

4. 회고

- 난 1)번 방법으로 풀긴했는데 음... 2)번 방법이 좀 더 확실할 것같다. 

  1)번은 배열 크기를 알 수가 없으므로

소스코드 : 1)번 방법

#include<iostream>
#include<vector>
using namespace std;

int p;
vector<int> a(300000, -1);

int cal(int num){
	int result = 0;
	while (num){
		int temp = 1;
		int mul = num % 10;
		for (int i = 0; i < p; i++)
			temp *= mul;
		result += temp;
		num /= 10;
	}
	return result;
}

int dfs(int num, int cnt){
	if (a[num] != -1)
		return a[num];

	a[num] = cnt;

	return dfs(cal(num), cnt + 1);
}

int main(void){
	int temp;
	cin >> temp >> p;

	cout << dfs(temp, 0) << "\n";
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]