[백준][C++] 4673 문제 : 셀프 넘버

이 글은 백준을 공부하며 작성한 글입니다. 

 

4673번: 셀프 넘버

 

목차.

1. 4673번 : 셀프넘버
2. 소스코드
3. 코드분석

 

4673번 : 셀프넘버 

문제

셀프 넘버는 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

입력

입력은 없다.

 

출력

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

 

예제

 

소스코드

#include<iostream>

using namespace std;

int CalculateSelfNum(int value)
{
    int sum = value; // 초기값을 value로 설정

    while (value > 0)
    {
        sum += value % 10; // 각 자리수를 더함, 85가 들어오면 +5
        value /= 10; //그리고 8을 더해서 결과적으로 85+8+5를 하고 생성자를 구함
    }

    return sum;
}

int main()
{
    const int RANGE = 10000;
    int* arr = new int[RANGE + 1] {}; // 배열 크기 조정 및 초기화

    for (int i = 1; i <= RANGE; i++)
    {
        int selfNum = CalculateSelfNum(i);
        if (selfNum <= RANGE) // 배열 인덱스 초과 방지
            arr[selfNum] = 1; // 생성자가 있는 경우 1로 설정
    }

    for (int i = 1; i <= RANGE; i++)
    {
        if (arr[i] == 0) // 생성자가 없는 경우 출력
        {
            cout << i << endl;
        }
    }

    delete[] arr; // 동적 메모리 해제

    return 0;
}

 

코드분석

 

문제를 보면 생성자가 없는 셀프넘버를 구하라고 했다.

1~10000까지 구해야 하니 

int* arr = new int [RANGE + 1] {};

동적으로 배열을 할당하였고 RANGE로 한다면 9999까지만 생성되니까 +1을 해주었다

물론 RANGE를 처음부터 10001로 해주어도 무관하다.

 

for 반복문을 통해서 1부터 10000의 값을 CalculateSelfNum 함수에 매개변수로 넣고 생성자를 반환한다.

 

이때 분명 생성자가 10000이 넘어가는 경우도 있을 테니 넘어가지 않는 경우에만 

arr 배열의 selfNum 위치에 0을 1로 변경해 주어서 

 

최종적으로 1이 아니라 0인값을 반복문으로 출력해 주는 코드이다.