[백준] 4673번 셀프 넘버 C, Python 해설

에라토스테네스의 체 알고리즘으로 분류된 문제이다.

하지만 C언어로 푼 다면 단순하게 자신만의 알고리즘으로도 풀이가 가능하다.

 

풀이

---

문제에서 정의한 셀프 넘버는 생성자가 없는 숫자를 뜻한다.

문제에서 제공된 함수 d(n)을 구현하고, 1부터 10000까지 반복하여 생성자가 존재하는 숫자에 대해서는 미리 체크한 뒤 체크되지 않은 수만 출력하는 알고리즘으로 문제에 접근하였다.

- C 정답 코드

#include <stdio.h>
int self_num(int num) {
	int sum = num;
	while (num != 0) {
		sum += num % 10;
		num /= 10;
	}
	return sum;
}

int main() {
	int i = 1, tmp;
	char arr[10001] = { 0, };
	for (; i < 10001; i++) {
		tmp = self_num(i);
		if (tmp < 10001)
			arr[tmp] = 1;
	}

	for (i = 1; i < 10001; i++) {
		if (!arr[i])
			printf("%d\n", i);
	}

	return 0;
}

 

- Python 정답 코드

def self_num(num):
	s = num
	while num != 0:
		s += num % 10
		num //= 10
	return s

arr = [True for i in range(1,11000)]

for i in range(1,10000):
	arr[self_num(i)] = False

for i in range(1,10000):
    if arr[i] : print(i)

 

결과 인증

---

사실 에라토스테네스의 체 알고리즘을 적용하여 풀어봤는데 위 코드들 보다 시간이 오래 걸려서 아직 제출하지 못했다.

글을 마무리하고 좀더 깊게 공부하러 가봐야겠다.