취미로 코딩하기

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

이번에 볼 문제는 백준 10434번 문제인 행복한 소수이다.
문제는 아래 링크를 확인하자.

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

주어진 수가 행복한 소수인지를 판별하는 것은 (1)주어진 수가 소수인지와 (2)주어진 수가 행복한 수인지를 각각 구해 해낼 수 있다. 이 중 (1)은 에라토스테네스의 체 등을 이용하는 것으로 간단히 할 수 있다.

모든 10000 이하의 자연수 n에 대하여 f(n)을 각 자리의 제곱의 합을 나타내는 함수로 정의할 때 f(n)의 값은 1 이상 324 이하가 됨을 관찰하자. 또한 f(n)은 항상 양의 정수이므로 이를 이용하면 수열 n, f(n), f(f(n)), f(f(f(n)))... 은 어떤 항부터 주기를 갖게 됨을 알 수 있다. 이 주기가 1이 반복되는 것이면 행복한 수, 그렇지 않다면 행복한 수가 아닌 수가 됨은 간단히 알 수 있다.

위 내용을 이용해 (1)과 (2)의 조건을 만족하는지를 판별하고 문제를 해결하자. 글쓴이는 10000 이하의 모든 양의 정수에 대하여 각 수가 소수인지 및 행복한 수인지를 미리 구해두는 방식으로 문제를 해결하였다.

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

#include <iostream>
using namespace std;

int P;
int sieve[10001];
int hap[10001];

int dfs(int cur) {
	hap[cur] = 2;
	int tmp = cur, nxt = 0;
	while (tmp) {
		nxt += (tmp % 10) * (tmp % 10);
		tmp /= 10;
	}

	if (hap[nxt]) return hap[cur] = hap[nxt];
	else return hap[cur] = dfs(nxt);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	sieve[1] = 1;
	for (int i = 2; i < 10001; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 10001; j += i) sieve[j] = 1;
	}

	hap[1] = 1;
	for (int i = 2; i < 10001; i++) {
		if (hap[i]) continue;
		dfs(i);
	}

	cin >> P;
	while (P--) {
		int T, x; cin >> T >> x;
		if (hap[x] < 2 && !sieve[x]) cout << T << ' ' << x << " YES\n";
		else cout << T << ' ' << x << " NO\n";
	}
}