취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2331번 문제인 반복수열이다.
문제는 아래 링크를 확인하자.

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

set을 이용하면 A부터 시작하여 수열 D를 생성해나가면서 나오는 모든 원소를 set을 이용하여 관리할 수 있다. 수열 D의 생성을 중복원소가 나올 때까지 진행하고, 그 중복 원소부터 해당 원소가 다시 나올 때까지 D를 더 생성해보는 것으로 주기의 길이를 구해 문제의 답을 계산해낼 수 있다.

모든 여섯자리 수에 대하여 D의 다음 원소의 크기는 일곱자리를 넘어갈 수 없다는 관찰과 비둘기집의 원리를 이용하면 위 풀이가 제한시간 내에 돌아간다는 것을 간단히 보일 수 있다.

아래는 제출한 소스코드이다.

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

set<int> st;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int A, P; cin >> A >> P;
	while (st.find(A) == st.end()) {
		st.insert(A);
		int tmp = 0;
		while (A) {
			int d = A % 10; A /= 10;
			int dtmp = 1;
			for (int i = 0; i < P; i++) dtmp *= d;
			tmp += dtmp;
		}
		A = tmp;
	}

	int X = A;
	int tmp = 0;
	while (A) {
		int d = A % 10; A /= 10;
		int dtmp = 1;
		for (int i = 0; i < P; i++) dtmp *= d;
		tmp += dtmp;
	}
	A = tmp;
	int cnt = 1;
	while (A != X) {
		cnt++;
		int tmp = 0;
		while (A) {
			int d = A % 10; A /= 10;
			int dtmp = 1;
			for (int i = 0; i < P; i++) dtmp *= d;
			tmp += dtmp;
		}
		A = tmp;
	}

	cout << st.size() - cnt;
}