[C++] 백준 4673번 셀프 넘버

1. 문제이해

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

4673번: 셀프 넘버

 

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

이때, n을 d(n)의 생성자라고 할 때, 생성자가 없는 숫자를 셀프 넘버라고 한다.

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하는 것이 목표이다.

 

 

 

2. 문제풀이

 

10000 이하의 생성자가 없는 숫자, 셀프 넘버인 숫자들을 출력하는 것이 목표이다.

예를 들어, 62라는 숫자를 이용해 만들 수 있는 숫자는 62 + 6 + 2 = 70 이 있다.

이때, 62는 70의 생성자이므로, 70은 생성자가 1개 이상, 셀프 넘버가 아니게 된다.

또 다른 예로, 53이라는 숫자를 이용해 만들 수 있는 숫자는 53 + 5 + 3 = 61

이때, 53은 61의 생성자이므로, 61은 생성자가 1개 이상, 셀프 넘버가 아니게 된다.

 

이런식으로, 양의 정수 n이 주어지면, 해당 숫자를 이용해 만들 수 있는 숫자를 도출할 수 있게 되고,

이를 통해 도출된 숫자는 생성자가 하나 이상 존재하는 것이므로 셀프넘버가 아니게 된다.

이 점에 착안하여, 필자는 셀프 넘버를 찾기보다는,

셀프 넘버가 아닌 숫자를 찾아 제외하는 식의 알고리즘을 이용해 코드를 구현해보았다.

구현한 코드는 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

// 셀프 넘버를 찾아 출력하는 함수
int find_self_number() {
	// 100000까지의 숫자를 모두 false로 설정
	// 단, 0은 양의 정수가 아니므로, 0은 true로 바꾸고 반복문 시작
	bool check_num[10001] = { false, };
	check_num[0] = true;
	
	// 반복문을 통해 셀프넘버가 아닌 숫자는 true값으로 초기화
	for (int i = 1; i <= 10000; i++) {
		int sum = i;            // 각 자릿수의 합
		int share = i;          // 10으로 나눈 몫 
		int remainder;          // 10으로 나눈 나머지 (각 자릿수)

		// 몫이 0이 될 때까지 10으로 나눠가며 자릿수를 구하고, 합을 구한다.
		while (share != 0) {
			remainder = share % 10;
			sum += remainder;
			share = share / 10;
		}
		
		// 만약 자릿수의 합이 10000을 넘는다면, 
		// 배열의 범위를 넘어서는 값에 접근하는 것이므로 제외
		if (sum > 10000) {
			continue;
		}
		// 어떤 숫자의 자릿수의 합으로 이루어진 숫자,
		// 즉, 셀프넘버가 아닌 숫자는 true로 바꾸어줌.
		else {
			check_num[sum] = true;
		}
	}

	// true 값으로 바뀐 숫자는 셀프넘버가 아니므로
	// false 값인 숫자만 출력 -> 셀프넘버
	for (int i = 0; i <= 10000; i++) {
		if (check_num[i] == false) {
			cout << i << "\n";
		}
	}

	return 0;
}

int main() {

	find_self_number();

	return 0;
}

(주석을 삭제한 코드는 아래에 따로 적어두었습니다.😊)

find_self_number 라는 셀프 넘버를 찾아 출력하는 함수를 정의하고,

메인함수에서는 이를 호출하기만 하는 식으로 코드를 작성했다.

 

find_self_number 함수는, 함수명 그대로 셀프 넘버를 찾는 사용자 설정 함수이다.

해당 함수에서는 먼저, check_num[i] 이라는 bool 형 배열을 선언해주었다.

check_num[i] 배열은 양의 정수 i가 셀프 넘버인지를 체크하는 배열로,

모든 연산이 끝나고 양의 정수 i가 셀프 넘버라면 false 값, 셀프 넘버가 아니라면 true 값으로 초기화되도록 했다.

 

먼저, 어떤 양의 정수 i가 셀프 넘버인지 모르므로, 모든 값을 false 값으로 설정해준다.

(배열은 0번째부터 시작하고, 0은 양의정수가 아니고, 셀프넘버가 아니므로, true 값으로 설정해주었다.)

 

이후 for문을 통해 1부터 10000 까지 셀프 넘버를 찾는 연산을 수행한다.

각 자릿수의 합을 sum, 10으로 나눈 몫을 share, 나머지이자 각 자릿수를 remainder 라고 두고,

몫이 0이 될때까지 각 자릿수를 구해 sum에 더해주었다.

이렇게 구해진 sum값을 통해, i는 sum의 생성자가 되고, sum은 생성자가 1개 이상 있는 것이므로,

sum 값에 해당하는 check_sum 값을 true 로 바꾸어준다.

(만약 sum값이 10000을 넘어간다면, 배열의 범위를 초과하는 값에 접근하게되므로 연산수행 X)

 

위와 같이 1부터 10000까지의 숫자에 대해

셀프 넘버가 아닌 숫자를 찾아 false 값으로 바꾸는 연산을 수행하고 나면,

true 값으로 남겨진 숫자들이 셀프 넘버에 해당하게 되므로,

1부터 10000까지 true 값으로 남아있는 숫자를 출력한다.

 

 

주석 없는 코드는 바로 왼쪽 아래의 더보기 확인 바랍니다.😊

<주석 없는 코드>

#include <iostream>
using namespace std;

int find_self_number() {
	bool check_num[10001] = { false, };
	check_num[0] = true;
	
	for (int i = 1; i <= 10000; i++) {
		int sum = i;           
		int share = i;         
		int remainder;         

		while (share != 0) {
			remainder = share % 10;
			sum += remainder;
			share = share / 10;
		}
		
		if (sum > 10000) {
			continue;
		}
		else {
			check_num[sum] = true;
		}
	}

	for (int i = 0; i <= 10000; i++) {
		if (check_num[i] == false) {
			cout << i << "\n";
		}
	}

	return 0;
}

int main() {

	find_self_number();

	return 0;
}

 

 

---

주석 없는 코드를 더보기란에 두는게 좋을까요..? 따로 그냥 밑에 적어두는게 좋을까요..? 🤔

질문이나 지적은 언제나 감사하게 받고있습니다.😌