[Baekjoon] 2331번: 반복수열

 

 

 

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

2331번: 반복수열

 

---

 

문제 해결 과정

착안

문제에서 주어진 과정을 통해 숫자를 만들어 어떠한 컨테이너에 요소로서 순차적으로 추가하여 수열을 만든다고 가정하면, 반복수열이 처음 형성되는 숫자가 입력되는 순서가 몇 번째인지만 알면 반복수열을 제외한 수열의 길이를 쉽게 알 수 있다.

 

이를 구현하기 위해 중복된 키 값을 허용하지 않는 컨테이너인 std::unordered_map<> 클래스를 활용하고자 하였다. Key 는 만들어지는 숫자로, Value는 해당 숫자가 몇 번째로 입력받는지를 계산하여 해당 컨테이너에 추가하고자 하였다. try_emplace() 함수를 통해 요소가 새로 추가되지 않았을 경우(즉, 이미 수열에 입력된 숫자 중에서 처음으로 반복되는 숫자가 다시 입력되는 경우), 해당 요소가 처음 들어온 순서가 몇 번째였는지를 출력하여 해결하고자 하였다.

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <unordered_map>
#include <string>
#include <cmath>

using namespace std;

int main()
{
	int A, P;
	cin >> A >> P;

	unordered_map<int, int> Sequences;

	int i = 0;
	while (true)
	{
		int size = Sequences.size();
		Sequences.try_emplace(A, i++);

		if (Sequences.size() == size)
		{
			cout << Sequences.at(A) << "\n";
			return 0;
		}

		string a = to_string(A);
		A = 0;
		for (char c : a)
			A += (int)pow(c - '0', P);
	}
}

 

실행 결과