[C++] 백준 2331: 반복수열

문제

[C++] 백준 2331: 반복수열 SILVER 4
https://www.acmicpc.net/problem/2331

 

---

 

접근 방법

이 문제는 수열을 생성하다가 중복이 처음 발생하는 지점 이전까지의 원소 개수를 구하는 문제이다.

수열은 다음 규칙으로 만들어진다.
현재 수의 각 자릿수를 P제곱한 값들을 모두 더해 다음 수를 만든다.

 

이를 구현하기 위해

1. 시작 값 a를 벡터 d에 넣고
2. value() 함수를 이용해 다음 값을 계속 생성한다.
3. 이미 나온 값인지 빠르게 확인하기 위해 boolean 배열(check) 로 방문 여부를 관리한다.
4. 처음으로 중복이 발생하면 수열 생성을 멈춘다.
5. 중복된 값이 처음 등장했던 위치를 찾아, 그 인덱스가 곧 정답이 된다.

 

구현 시 주의할 점

• 자릿수 계산은 % 10과 / 10을 이용해 하나씩 분리하며 처리한다.
• 같은 값이 다시 등장하는 순간이 중요하므로, 다음 값을 push한 뒤 방문 여부를 확인하는 것이 좋다.
• check 배열 크기는 조건의 최댓값인 4 * (9 ^ 5) = 236196에서 +1을 해준 236197으로 지정하는 것이 안전하다.
  (A의 최댓값이 9999, P의 최댓값이 5)

 

---

 

코드

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

int value(int n, int p)
{
	int ret = 0;

	while (10 <= n)
	{
		int t = n % 10;
		ret += pow(t, p);

		n /= 10;
	}
	ret += pow(n % 10, p);

	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	bool check[236197] = { false, };
	int a = 0, P = 0;
	cin >> a >> P;

	vector<int> d;
	d.push_back(a);
	check[a] = true;

	int index = 1;
	while (1)
	{
		int next = value(d[index - 1], P);
		d.push_back(next);

		if (check[next] == true)
			break;

		check[next] = true;
		index++;
	}
	for (int i = 0; i < index; i++)
	{
		if (d[i] == d[index])
		{
			cout << i;
			break;
		}
	}

	return 0;
}