[C/C++] BOJ 문제번호 4673 셀프 넘버

BOJ 문제번호 4673

  이 문제를 접근할 때, 소수를 구하는 문제가 생각났다. 소수를 구하는 경우 에라토스테네스의 체 방식을 사용했었는데 그것을 응용해보았다. 

  에라토스테네스의 체란, 고대 그리스 수학자 에라토스테네스가 발견한 방식으로, 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 가장 첫번째로 2는 소수이므로 2를 저장한다. 그리고 나서 2를 제외한 모든 2의 배수를 지워나간다. 마찬가지로 3은 지워지지 않은 숫자로 소수이다. 3을 저장한 후 2와 같은 방법으로 3의 배수를 모두 지워나간다. 이렇게 지워지지 않은 수를 저장하고 본인을 제외한 본인의 배수들을 지워나게 되면 소수를 구할 수 있다.  

 

  이 방식을 코드화 하면, 구하고자 하는 구간의 수만큼의 배열을 bool형으로 만든다. 예를 들어, 100까지 구간의 수 중에 소수를 찾고자 할때 bool prime_number[100]을 선언한다. 초기에 모든 값을 true로 초기화 해준 후 0번째 배열의 원소는 false로 만들어준다. 그 이유는 배열은 0부터 99의 index를 갖게 되는데, 우리는 1부터 100까지의 수를 원하기 때문에 index에 +1을 해서 생각을 해주어야 한다. 만약 이 방법이 헷갈릴 경우 bool prime_number[101]로 만든 후 1~100의 index를 활용하여도 좋다. 첫번째 원소를 false로 초기화해주는 이유는 1은 소수가 아니기 때문이다. 이제 위의 방식을 반복하면 되는데 두번째 원소부터 본인을 제외한 2의 배수들의 원소들을 false로 만들어준다. 세번째 원소도 똑같은 작업을 반복하는데, 이때부터 해당 원소가 true일 경우에만 그 원소의 배수들을 지워나가는 동작을 한다. 이 모든 반복이 끝났을 경우에 prime_number배열에는 소수인 숫자만 true로 남게 된다. 

 

  위의 개념을 문제에 적용시키면, 1부터 자기 자신과 각자리 숫자를 더해서 나온 값을 false로 지워주면 된다. 하지만 에라토스테네스의 체와는 다르게 1부터 원하는 구간의 수까지 규칙을 적용해야 한다는 점이다. 1부터 원하는 구간까지의 계산이 끝난 후 true의 값만 뽑아내게 되면 그 숫자들이 셀프 넘버이게 된다.

 

1. 10,000개의 배열을 선언 후 false로 초기화

2. 두번째 원소의 배열부터 (자기자신) + (각 자리수의 합)에 해당하는 원소를 true로 바꿔주고, 바뀐 값을 이용해 다시 (자기자신) + (각 자리수의 합)의 원소를 true로 바꿔줌. 대신 이 값이 10,000을 넘어가선 안된다.

3. 세번째 원소가 false일 경우에만 2번의 과정을 반복.

4. 10,000번째 원소까지 2~3번의 과정을 반복.

5. 첫번째 원소부터 10,000번째 원소까지 false인 원소만 출력.

 

# 만약 에라토스테네스의 체의 방식대로 self number가 true가 되게 짤 경우 배열을 선언하고 for문을 이용하여 배열을 하나하나 true로 초기화 시켜주거나, memset함수를 이용하여 true로 초기화 시켜주어야 한다. 그러지 않을 경우 원하는 결과가 나오지 않는다.

# memset(check, true, sizeof(check)); 로쓰면 됨. visual studio의 경우 memset을 쓸때 오류가 안나지만 백준에서 채점할 경우 컴파일 오류가 나기 때문에 "#include "를 선언해 주어야 한다.

# for문으로 초기화하는 것 보다 memset이 속도가 더 빠르다고 한다.

 

#include <iostream>

int main() {
	bool check[10000] = { false, };			// self number를 찾아낼 배열
	int temp, temp_10, temp_100, temp_1000, temp_10000;			// 각 자릿수 변수
	int mod, mod_10, mod_100, mod_1000;		// 자릿수로 나눈 나머지를 저장하는 변수

	for (int i = 1; i <= 10000; i++) {
		temp = i;			// 계산할 값을 temp에 입력
		while (!check[i - 1] && temp <= 10000) {			// 해당 index가 false이고 최대 값 10000을 넘지 않을 경우 반복
			temp_10000 = temp / 10000;
			mod_1000 = temp % 10000;
			temp_1000 = mod_1000 / 1000;
			mod_100 = mod_1000 % 1000;
			temp_100 = mod_100 / 100;
			mod_10 = mod_100 % 100;
			temp_10 = mod_10 / 10;
			mod = temp % 10;

			temp = temp + temp_10000 + temp_1000 + temp_100 + temp_10 + mod;			// 자기 자신과 각 자릿수를 더하는 과정

			if(temp <= 10000)			// temp가 10000의 범위 안에 있을 때, 그 temp값은 self number가 될 수 없으므로 true로 바꿔줌
				check[temp - 1] = true;				
		}
	}
	int i = 0;
	while (i < 10000) {				// 계산 결과 후 모든 배열을 조사하여 false인 것들을 탐색 후 출력 (false = self number)
		if (!check[i])
			printf("%d\n", i + 1);
		i++;
	}

}

채점 결과