문제

풀이

많이 고민했던 문제다. 푸는데 오래 걸렸는데 다 풀고나서 다시 보니 그렇게 어려운 문제가 아니었다. ㅠㅠ
전체 코드는 다음과 같다.

#include <iostream>
using namespace std;

int d(int num)
{
  int sum = num;

  while(1)
  {
    if(num == 0)
    {
      break;
    }

    sum += (num % 10);
    num /= 10;
  }

  return sum;
}

int main()
{
  bool nums[100001]; // 인덱스가 셀프 넘버가 아니면 true, 셀프 넘버면 false를 반환
  int idx;

  for(int i = 0; i < 10001; i++)
  {
    idx = d(i);

    if(idx < 10001)
    {
      nums[idx] = true;
    }
  }

  for(int i = 0; i < 10001; i++)
  {
    if(nums[i] == false)
    {
      cout << i << endl;
    }
  }

  return 0;
}

하나씩 살펴보자.

int d(int num)
{
  int sum = num;

  while(1)
  {
    if(num == 0)
    {
      break;
    }

    sum += (num % 10);
    num /= 10;
  }

  return sum;
}

문제의 설명에 나온 함수 d(n)이다. 함수 d의 리턴값 sum은 num + num의 n번째 자리 ... 같은 형태로, 함수의 인수로 주어진 num에다 num의 각 자리수를 더한다. 그러므로 sum에 기본적으로 num의 값을 할당해주고 시작한다.

각 자리수를 구해서 더해야하기 때문에 주어진 num의 10으로 나눈 나머지(일의 자리 수)를 sum에 더하고, num을 10으로 나눠가면서 num 0이 될 때까지 계속 반복한 후 sum을 리턴한다.

  bool nums[100001]; // 인덱스가 셀프 넘버가 아니면 true, 셀프 넘버면 false
  int idx;

  for(int i = 0; i < 10001; i++)
  {
    idx = d(i);

    if(idx < 10001)
    {
      nums[idx] = true;
    }
  }

10,000보다 작거나 같은 셀프 넘버를 출력하므로, 10001의 크기를 가지는 부울 배열을 만든다. 배열의 각 요소는 인덱스에 해당하는 수가 셀프 넘버면 false, 셀프 넘버가 아니면 true를 저장한다.

for 안에서 0부터 10000까지의 수를 함수 d에 전달해 num과 num의 각 자리수의 합을 받아낸다. 그리고 그걸 idx 변수에 저장한다.
idx의 해당하는 수들은 모두 셀프 넘버가 아니므로 nums 배열에서 idx번째의 요소는 true로 만든다.

  for(int i = 0; i < 10001; i++)
  {
    if(nums[i] == false)
    {
      cout << i << endl;
    }
  }

0부터 10000 사이의 수를 탐색하면서 셀프 넘버인 수(nums의 값이 false인 요소의 인덱스)를 출력한다.