[백준] 4673번 셀프 넘버 C++ 문제 풀이 함수

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

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

입력

입력은 없다.

출력

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

---

예제 입력 1

---

예제 출력 1

1

3

5

7

9

20

31

42

53

64

|

| <-- a lot more numbers

|

9903

9914

9925

9927

9938

9949

9960

9971

9982

9993

---

문제 풀이

#include <iostream>
using namespace std;
int main(void){
    int arr[10000] = {1,};
    int temp;
  for(int i = 1; i < 10000; i++){
      if(i < 10){
        arr[i+i] = 1;
        continue;
      }
      else if(i < 100){
        arr[i + i/10 + i%10] = 1;
                continue;
      }
      else if(i < 1000){
        arr[i + i/100 + i%100/10 +i%10] = 1;
                continue;
      }
      else if(i < 10000){
        temp = i + i/1000 + i%1000/100 + i%100/10 + i%10;
        if(temp < 10000){
            arr[temp] = 1;
            continue;
        }
      }
  }
  
  for(int i = 1; i < 10000; i++)
        if(!arr[i])
        cout<<i<<"\n";
}

각 자리 수마다 if 문으로 나눠서 처리하였습니다.

 

어떤 숫자에서 생성자를 도출해서 셀프 넘버인지 판별하는 것보다는,

셀프 넘버가 아닌 값들을 모두 찾는 방식으로 접근하였습니다.

위에 쓰여있는 수열 공식을 사용하여 나온 값을 인덱스로 사용하여

해당 배열의 값을 1로 바꾸어줬습니다.

이렇게 하면 1이 아닌 값들은 생성자가 없는 숫자들이므로 셀프 넘버라 할 수 있습니다.

 

천의 자리는 이런 공식을 사용하면 10000 이상의 값이 나오기 때문에 따로 분기 처리를 해주셔야 합니다.

 

문제에서 범위가 10000을 포함하지만 이미 출력 부분에 10000이 포함되지 않았기 때문에 등호 표시를 생략하였습니다.

 

마지막에 for 문을 통해 0인 값들만 출력하면 정답이 됩니다.

 

 

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

4673번: 셀프 넘버