BOJ 4673번 셀프 넘버

BOJ 4673번 셀프 넘버 풀이 소스코드

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

풀이 1

#include <iostream>

int _d(int n) {
	return (n == 0) ? 
		0 : (n%10 + _d(n/10));
}

int d(int n) {
	return n + _d(n);
}

int main() {

	int constructor = -1; 
	int upper_limit = 10000;
	bool is_self_number[upper_limit+1];

	for (int i = 0; i <= upper_limit; i++) {
		is_self_number[i] = true;
	}

	// O(n^2)
	for (int i = 1; i <= upper_limit; i++) {
		constructor = d(i);	
		while (constructor <= upper_limit) {
			is_self_number[constructor] = false;
			constructor = d(constructor);
		}
	}

	for (int i = 1; i <= upper_limit; i++) {
		if (is_self_number[i]) {
			std::cout << i << std::endl;
		}
	}

	return 0;
}

 

풀이 2

굳이 반복문을 중첩해서 돌릴 필요가 없다.

#include <iostream>

int _d(int n) {
	return (n == 0) ? 
		0 : (n%10 + _d(n/10));
}

int d(int n) {
	return n + _d(n);
}

int main() {

	int constructor = -1; 
	int upper_limit = 10000;
	bool is_self_number[upper_limit+1];

	for (int i = 0; i <= upper_limit; i++) {
		is_self_number[i] = true;
	}

	// O(n)
	for (int i = 1; i <= upper_limit; i++) {
		constructor = d(i);	
		if (constructor <= upper_limit) {
			is_self_number[constructor] = false;
		}
	}

	for (int i = 1; i <= upper_limit; i++) {
		if (is_self_number[i]) {
			std::cout << i << std::endl;
		}
	}

	return 0;
}