알고리즘(C++) / 백준 2331 : 반복수열

2331

boj.kr/2331

2331번: 반복수열

 

문제

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

• 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)가 주어진다.

 

출력

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

 

코드

이번 문제는 DFS를 사용할 수도 있고 사용하지 않을 수도 있다. 

그래서 두 경우 다 문제를 풀어보았다. 

• DFS

//2331 반복순열
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstdlib>
using namespace std;
int P;
int visited[300000] = { 0, };
vector <int> v;

void DFS(int A) {
	visited[A]++;

	if (visited[A] == 2) {
		for (int i = 0; i < v.size(); i++) {
			if (v[i] == A) {
				cout << i << "\n";
				return;
			}
		}
	}
	
	int num = 0;
	while (A > 0) {
		num += pow((A % 10), P);
		A /= 10;
	}

	v.push_back(num);
	DFS(num);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int A;
	cin >> A >> P;

	v.push_back(A);

	DFS(A);

	return 0;
}

DFS를 사용하여 구현하였다. 

입력받은 수 A를 DFS에 인자로 넣는다. 

A의 방문수를 증가 시켜준다. 

각 자리의 숫자를 P번 곱한 수들의 합을 벡터에 넣어주고, DFS에 인자로 넣는다.

이 때 두 번 방문한 수는 반복이 되는 첫번째 숫자이다. 벡터에서 이 수가 나오는 위치를 찾아 수열에 남게 되는 수들의 개수를 출력한다. 

 

• DFS X

//2331 반복순열
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstdlib>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string A;
	int P;
	vector <string> v;
	int index;
	
	cin >> A >> P;
	v.push_back(A);

	while (1) {
		int num = 0;
		for (int i = 0; i < A.size(); i++) {
			num += pow(A[i]-48, P);
		}
		for (int i = 0; i < v.size(); i++) {
			if (v[i] == to_string(num)) {
				cout << i << "\n";
				return 0;
			}
		}

		A = to_string(num);
		v.push_back(A);

	}

	return 0;
}

DFS를 사용하지 않고 구현할 수 있다.

여기서 string으로 입력받았지만 앞서 구현한 거 처럼 int형으로 입력을 받아올 수도 있다. 

DFS대신 while문으로 반복되는 부분이 나올 때까지 반복한다.

각 자리의 숫자를 P번 곱한 수들의 합을 벡터에 넣어준다.

이 때 구한 수가 이미 방문하였다면 위치를 출려한다.

 

결과

 

고찰

이번 문제는 처음에 DFS를 사용하지 않고 구현할 수 있었다.

어떤문제에 DFS를 이용하여 구현할지 잘 생각해봐야한다.