[백준/BOJ] 4673번 셀프 넘버 (C/C++)

백준 온라인 저지(BOJ) 4673번 셀프 넘버

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

4673번: 셀프 넘버

* 사용언어 : C언어, C++

 

1. 문제

양의 정수 n 에 대해서 d(n) 은 n 과 n 의 각 자리수를 더하는 함수

n 을 d(n) 의 생성자라고 하는데, 생성자가 없는 숫자를 셀프 넘버라고 할 때,

10,000 보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력

 

2. 풀이

함수 카테고리에 속하는 문제라서 일단 d(n) 을 함수로 구현하고 시작했습니다.

입력받은 숫자(n)에 1의 자리(n % 10)를 더해주고 n 을 10 으로 나눈 뒤,

n 이 0이 될 때까지 반복하는 방식으로 구현했습니다.

 

하지만 문제는 d(n) 이 아닌 d(n) 이 없는 n 을 출력하는 문제입니다.

그래서 d(n) 에서 n 을 어떻게 찾아서 출력할까를 오랜 시간 고민했는데 결론이 나지 않았습니다.

 

그러다가 문득 n 을 1부터 10,000까지 반복하면서 d(n) 을 만들고,

d(n) 이 한 번도 생성되지 않으면 셀프 넘버로 출력하자는 결론을 냈습니다.

 

예를 들어, n 이 24 라면 d(n) 은 24 + 4 + 2 = 30 이 됩니다.

30은 생성자가 있는 숫자이므로 미리 생성해둔 배열의 30번째 자리에 체크를 해둡니다.

(셀프 넘버가 아니라는 뜻으로 1 로 설정)

 

n 이 d(n) 보다 클 수 없기 때문에

n 을 1부터 10000까지만 반복하면 d(n) = 10000 까지 모두 확인한 셈이 됩니다.

 

확인이 완료된 후에는 한 번도 체크가 안 된,

즉 배열의 값이 0 인 자리의 index 를 출력합니다.

 

3. 코드

#include <stdio.h>

const int LM = 10000;
int a[LM];

int d(int n) {
	int ret = n;
	while (n) {
		ret += n % 10;
		n /= 10;
	}
	return ret;
}

int main() {
	for (int i = 0; i < LM; ++i) {
		int ret = d(i);
		if (ret < LM) a[ret] = 1;
	}

	for (int i = 0; i < LM; ++i) {
		if (!a[i]) printf("%d\n", i);
	}
	return 0;
}