[BOJ-4673] 셀프 넘버

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

4673번: 셀프 넘버

 

2019년도 상반기 모 기업의 코딩 테스트 문제로 나왔었던 문제이다.

 

당시 시험장에서는 더 높은 10만이었나? 아무튼 더 높은 수의 범위를 요구했었던 것으로 기억한다.

 

-----------------------------------------------------------------------------------------------------------------

 

- 문제 풀이

1. 일단 문제에서 정의한 d[n]을 모두 구해준다 10000까지이고 제일 많이 반복되는 케이스가 5회도 채 안되기 때문에 최악의 경우를 고려해보면 50000이다. 따라서 최악의 경우를 고려하더라도 시간복잡도상 문제가 되지 않기 때문에 재귀로 구한다.

 

2. 정의한 d[n]중 생성자가 없는 수가 셀프 넘버이다. 이 수를 찾는다.

 

3. 찾은 수를 출력한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int d[10001];
int check[10001];

void self_number(int num, int ori) {

	if (num == 0) return;

	int temp = num % 10;
	d[ori] += temp;

	num /= 10;
	self_number(num, ori);;
}

int main(void) {

	for (int i = 1; i <= 10000; i++) {
		d[i] += i;
		self_number(i, i);
	}

	for (int i = 1; i <= 10000; i++) {
		if (d[i]) {
			check[d[i]] = 1;
		}
	}

	for (int i = 1; i <= 10000; i++) {
		if (check[i] == 0) {
			printf("%d\n", i);
		}
	}

	getchar();
	getchar();

	return 0;
}

 

문제의 난이도는 어렵지 않은 편이니 주석은 생략~!!!