[C/C++] 백준 10434번 행복한 소수

 

 

 

<CODE>

#include<stdio.h>
#include<math.h>
#include<memory.h>

int dp[10000]; // 제곱의 합이 주기적으로 도는지, '1'로가는지 기록하기 위한 배열
int a4, a3, a2, a1, N;

int check(int n) // 각 자리 수 제곱의 합 구하는 함수
{
	if (n < 10)
	{
		a1 = n;

		N = int(pow(a1, 2));
		return N;
	}
	else if (n < 100)
	{
		a2 = int(n / 10);
		a1 = n % 10;

		N = int(pow(a1, 2) + pow(a2, 2));
		return N;
	}
	else if (n < 1000)
	{
		a3 = int(n / 100);
		a2 = int((n % 100) / 10);
		a1 = n % 10;

		N = int(pow(a1, 2) + pow(a2, 2) + pow(a3, 2));
		return N;
	}
	else if (n <= 10000)
	{
		a4 = int(n / 1000);
		a3 = int((n % 1000) / 100);
		a2 = int((n % 100) / 10);
		a1 = n % 10;

		N = int(pow(a1, 2) + pow(a2, 2) + pow(a3, 2) + pow(a4, 2));
		return N;
	}
}

int Happy_Prime_Number(int n)
{
	/* 연산을 계속 하다보면 1로 가는 값이 있는 반면, 계속 주기적으로 루프를 도는
	값도 있으므로 n값이 변할때 마다 dp배열에 기록을 해준다('1' 표시).
	만약 연산을 하는데 dp[n]값이 이미 '1'로 기록되어 있다면 한 주기를 돈 것이므로 return 0을 해준다
	반대로 값이 n의 값이 '1'로 향하는 경우라면 n = 1일때 return 1을 한다. */
	
	while (1)
	{
		if (n == 1) return 1; // 행복한 소수
		else
		{
			if (dp[n] == 1) return 0; // 한바퀴 돌았다면 return 0
			else dp[n] = 1; // 처음 지나가면 '1' 기록
			n = check(n);
		}
	}

}

int main(void)
{
	int T, M, t; // 테스트케이스, input, t번째 케이스
	int num = 10000;
	int prime_number[10001] = { 1,1, };  // 소수 판별 배열, 배열값 [0]과 [1] 값을 1로 저장

	// 에라토스테네스의 체, 소수는 prime_number[i] = 0 으로 저장
	for (int i = 2; i < sqrt(num); i++)
	{
		if (prime_number[i] == 1) continue;
		for (int j = 2 * i; j <= num; j += i)
		{
			prime_number[j] = 1; // 소수가 아닌 것들 표시
		}
	}

	scanf("%d", &T);

	for (int i = 0; i < T; i++)
	{

		memset(dp, 0, sizeof(dp)); // 모든 배열 값 0으로 초기화

		scanf("%d %d", &t, &M);
		if (prime_number[M] == 0) // 소수인지 아닌지 판별
		{
			if (Happy_Prime_Number(M) == 1) // check함수 리턴값이 1 이면 행복한 소수O, 0이면 행복한 소수X
				printf("%d %d YES\n", t, M);
			else
				printf("%d %d NO\n", t, M);
		}
		else
		{
			printf("%d %d NO\n", t, M);
		}
	}


}

 

자꾸 런타임 에러가 발생하였는데 배열 크기가 커서인지, 배열 인덱스를 잘못참조하였느지, 재귀함수를 사용해서 그런지 잘 모르겠다. 무한 루프를 돌게되는 모든n값을 기록해서 Danamic Programming을 하고 싶었는데 막상 어떻게 구현해야할지 잘 떠오르지 않았다. 결국 while문으로 n값이 변할때마다 dp배열에 기록을 하였고 결과는 n값이 '1'로 가거나 한 바퀴를 돌거나 둘중 하나이기 때문에 행복한 소수를 판별할 수 있었다. 처음에는 소수 구하는 것을 반복문으로 해결 하려 하다가 예전에 "에라토스테네스의 체"를 검색해본 기억이 있어서 "에라토스테네스의 체" 방식을 이용하여 소수를 판별해내었다. 풀고나면 간단한 문제인데 구현 방법을 생각해내는데 시간이 좀 걸렸다. 아직은 실력이 많이 부족한거 같아 열심히 해야겠다고 느꼈다. 그래도 결국에는 풀어서 기분은 좋다 ㅎ

 

 

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

10434번: 행복한 소수