[백준 2331] 반복수열 (C++)

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

문제

---

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

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

예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=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)가 주어진다.

 

출력

---

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

 

문제 풀이

---

구현 문제.

 

문제에 주어진대로 각 자리의 숫자를 P번 곱해 새로운 수열을 만들면 된다. 문자열로 입력받으면 각 자리 숫자를 편하게 구할 수 있다. 반복되는 부분을 제거해야 하므로, <D[i], 인덱스 i>를 <K, V>로 가지는 map을 하나 만들어 중복 여부를 확인한다. 처음에는 <A, 1>을 맵에 넣어준다. 그리고 반복하여 D[i]를 구하며 맵에 데이터를 넣어준다. 만약 D[i]를 key로 하는 데이터가 맵에 존재한다면 D[i]부터는 반복되는 부분이다. D[i]의 인덱스 이전까지의 숫자가 수열에 남게 되는 개수가 된다.

 

아래는 코드.

#include <iostream>
#include <string>
#include <map>
using namespace std;

int pow(int N, int P)
{
	int temp = N;
	for (int i = 1; i < P; i++)
	{
		temp = temp * N;
	}
	return temp;
}

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

	string N;
	int P;
	int index = 1;
	cin >> N >> P;
	map<string, int> m;
	map<string, int>::iterator it;
	m.insert({ N, index });
	while (true)
	{
		int num = 0;
		for (int i = 0; i < N.length(); i++)
		{
			num += pow(N[i]-48, P);
		}
		N = to_string(num);
		index++;
		it = m.find(N);
		if (it == m.end())
		{
			m.insert({N, index});
		}
		else
		{
			cout << it->second - 1 << "\n";
			break;
		}
	}
	return 0;
}