[Silver V] 4673번: 셀프 넘버 (C++)

 

본문을 작성하는 사람은 주로 C++을 사용합니다.

---

1. 문제 개요

 1-1. 시나리오

 

 1-2. 입력

  X

 

 1-3. 출력

  10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다...

 

 1-4. 문제 링크

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

4673번: 셀프 넘버

---

2. 풀이

 2-1. 정리

 문제를 풀기 전에, "생성자"와 "셀프 넘버"에 대해서 제대로 알고 넘어갈 필요가 있습니다.

✨ 생성자란?
 기존의 숫자와 각 단위의 숫자를 더한 값을 d(n)이라 말합니다. 이 때 n값을 생성자라 말합니다.
이렇게 말하면, 이해도 잘 되지 않고 어렵지요?

"19" 라는 값을 기준으로 봐 보도록 합시다. 이때 19는 d(n) 값이에요.
19 값을 만들 수 있는 숫자는 "14"가 있어요.
 14 + 1(10의 자리) + 4(1의 자리) = 19
이렇게 되면, "14"는 "19"의 생성자라고 표현할 수 있습니다.

"21"이라는 값을 기준으로 또 본다면,
21 값을 만들 수 있는 숫자는 "15"가 있어요.
 15 + 1(10의 자리) + 5(1의 자리) = 21

19의 생성자는 14, 21의 생성자는 15.

또 깊게 들어 가 보면,
19 + 1(10의 자리) + 9(1의 자리) = 29
29의 생성자는 19이다.
이렇게도 표현할 수 있습니다. 이해가 되셨을까요?

원 숫자와 각 자릿수를 더한 값의 생성자가 되는 것이랍니다.
물론, 생성자는 여러 개가 될 수도 있어요.

 

✨ 셀프 넘버란?
 위 생성자를 보면서, 14와 15가 각각 19와 21의 생성자라면,
"20"의 생성자는 없을까? 라는 의문이 있을 수 있어요.

맞아요. 20은 생성자가 존재하지 않는 숫자입니다.
이런 것을 우린 셀프 넘버라고 말해요.

20, 31, 42 등, 직접 계산을 해 본다면 금방 아실 수 있을 내용이랍니다.

 

생성자와 셀프 넘버에 대해 어느정도 이해가 되셨다면,

먼저 (n) 값이 셀프 넘버인지 아닌지를 판별하는 함수를 만들어보도록 합시다.

#include <iostream>
using namespace std;

int getselfnumber(int number)
{
	int result = number;
	int whiler = number;

	while (whiler != 0)
	{
		result += whiler % 10;
		whiler /= 10;
	}

	return result;
}

 

number값 하나를 인자로 받는 getselfnumber 함수를 만들었습니다.

들어온 인자값을 생성자로 사용하는 숫자를 반환하도록 만들었습니다.

	while (whiler != 0)
	{
		result += whiler % 10;
		whiler /= 10;
	}

 

whiler는 각 자릿수의 숫자가 됩니다. (분해값)

result는 처음에 인자로 넘긴 number값이 그대로 들어 가 있어요.

위의 while문이 모두 실행되면, 인자로 들어온 number값과 각 자릿수의 숫자가 모두 더해진 값이 result에 저장되겠죠.

 

아래는 "15" 값을 입력했을 때 함수의 동작 순서를 표시합니다.

number 입력값 : 15인 경우 진행되는 순서

 result = 15
 whiler = 15

 result += whiler % 10  ::  result에 whiler를 10으로 나눈 나머지를 더한다. 이 때는 값이 5가 된다.
 whiler /= 10  ::  whiler를 10으로 나눈 값을 whiler에 덮어씌운다. 이미 사용 한 자릿수이기 때문!

 result = 20
 while = 1

 result += whiler % 10  ::  result에 whiler를 10으로 나눈 나머지를 더한다. 이 때는 값이 1이 된다.
 whiler /= 10  ::  whiler를 10으로 나눈 값을 whiler에 덮어씌운다. 이미 사용 한 자릿수이기 때문!

 result = 21
 whiler = 0 (정수형이기 때문에, 소수점은 자동 삭제!)

whiler의 값이 0이 되었기에 while문 탈출!
result값인 21을 반환하고 함수를 종료한다!

 

 

함수는 완성 되었으니, 이제 조금 무식한 방법을 사용해 보도록 할게요.

"셀프 넘버"는 생성자가 없는 숫자이니, 1부터 10,000 까지의 숫자를 위 함수에 넣었을 때, 한 번도 나오지 않는 숫자가

셀프 넘버인 것이니까, C++의 Vector 컨테이너를 사용 해 보도록 할게요.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<bool> result = vector<bool>(10001);

	for (int i = 0; i < 10001; i++)
	{
		result[getselfnumber(i)] = true;
	}
}

 

이렇게 한다면, 10,000개의 bool 배열 중 생성자가 있는 숫자는 true, 생성자가 없는 셀프 넘버는 false로 구분됩니다.

구분이 다 되었으니, 이제 콘솔창에 가시화만 해 주면 성공!

성공

= 코드 전문 =

#include <iostream>
#include <vector>

using namespace std;

int getselfnumber(int number)
{
	int result = number;
	int whiler = number;

	while (whiler != 0)
	{
		result += whiler % 10;
		whiler /= 10;
	}

	return result;
}

int main()
{
	vector<bool> result = vector<bool>(10001);

	for (int i = 0; i < 10001; i++)
	{
		result[getselfnumber(i)] = true;
	}

	for (int j = 0; j < result.size(); j++)
	{
		if (!result[j]) cout << j << "\n";
	}
}

 2-2. Github

https://github.com/devbini/Algorithm/tree/ea2d5e7c2527ef95756d2f21d118313f0d8d64b9/%EB%B0%B1%EC%A4%80/Silver/4673.%E2%80%85%EC%85%80%ED%94%84%E2%80%85%EB%84%98%EB%B2%84

---

 

3. 기억해 둘 부분

백터 컨테이너 활용, 조금 무식하게 푼 경향이 분명히 있다.

요구하는 알고리즘 "브루트포스", 완전 탐색의 가장 큰 치명적인 이슈, 문제의 복잡도...

우선 무식하게 풀었으니 문제가 요구하는 알고리즘은 충족했다고 생각한다.

 

두고두고 수정하고 최적화할 수 있는 방안을 더 찾아보고, 있다면 글을 수정하러 오도록 하겠다!

 

알고리즘의 <구현>은 대체로 문제를 잘 읽어보면 별도의 알고리즘이 필요하지 않다.

이런 문제들은 보다 문제를 이해하는 능력을 집중해서 키우도록 하자.