[백준] 4673 with C++

문제설명

---

입출력 예제

---

개념

　생성자가 없는 숫자인 셀프 넘버를 출력하는 문제다. 문제에서 알 수 있듯이 x라는 숫자가 있을 때, x의 각 자릿수들의 숫자와 x를 더한 숫자는 셀프 넘버가 아니게 된다. 따라서 bool 배열은 만들어 1부터 10000까지 상술한 규칙을 적용해, 해당하는 자리의 숫자를 true로 바꾼 후 false만 출력하면 된다.

---

풀이

풀이(1) string 이용하기

#include <iostream>
#include <string>
using namespace std;

int main()
{
	int num = 10000;
	bool selfnum[10000] = { false };

　max 숫자인 10000을 num으로 초기화하고, selfnum를 체크할 bool 배열 selfnum[]을 초기화한다.

 

	for (int i = 1; i < num; i++)
	{
		string n = to_string(i);
		int d = i;

		for (int j = 0; j < n.size(); j++)
			d += (n[j] - 48);

		if (d < num)
			selfnum[d] = true;
	}

　1부터 10000까지 셀프 넘버를 찾는 반복문이다. 먼저 이 반복문을 이해하기 전에 숫자를 문자열로 바꾸면 어떤 구조로 저장되는지 파악해야 한다.

 

 

　1000이라는 숫자를 문자열로 저장하면 다음과 같이 n[0] = '1', n[1] = '0', n[2] = '0', n[3] = '0' 으로 저장된다. 따라서 문자열의 크기만큼 반복을 돌릴 때 문자열에 임의 접근을 하여 48을 빼주면 자릿수별 정수가 더해지게 된다. 

 

		if (d < num)
			selfnum[d] = true;
	}

	for (int i = 1; i < num; i++)
	{
		if (selfnum[i] == false)
			cout << i << endl;
	}
}

　혹시 생성자가 10000보다 크게 된다면 문제의 범위를 초과하는 것이므로, 예외를 처리해준다. 그리고 다시 반복을 돌려 selfnum이 false인 것만 출력하면 문제를 해결할 수 있다.

 

총합본

#include <iostream>
#include <string>
using namespace std;

int main()
{
	int num = 10000;
	bool selfnum[10000] = { false };

	for (int i = 1; i < num; i++)
	{
		string n = to_string(i);
		int d = i;

		for (int j = 0; j < n.size(); j++)
			d += (n[j] - 48);

		if (d < num)
			selfnum[d] = true;
	}

	for (int i = 1; i < num; i++)
	{
		if (selfnum[i] == false)
			cout << i << endl;
	}
}

---

풀이(2)

#include <iostream>
using namespace std;

int main()
{
	int num = 10000;
	bool selfnum[10000] = { false };

	for (int i = 1; i < num; i++)
	{
		int n = i;
		int d = i;

		while (n != 0)
		{
			d += (n % 10);
			n /= 10;
		}

		if (d < num)
			selfnum[d] = true;
	}

	for (int i = 1; i < num; i++)
	{
		if (selfnum[i] == false)
			cout << i << endl;
	}
}

　자릿수를 더하는 알고리즘을 string이 아닌 while문으로 간단하게 처리한 코드다.