[C언어] 백준 4673번 : 셀프 넘버

백준 4673번 : 셀프 넘버

- 사용언어 : C언어

www.acmicpc.net/problem/4673

1. 문제

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

2. 코드

#include <stdio.h>

int main(void) {
    int self[15000];
    
    for(int i=0; i<15000; i++) self[i] = i+1;
    
    for(int i=0; i<10000; i++) {
        int m = i+1;
        int tmp = m;
        int a = 0, b = 0, result = 0;
        double c = 0;
        while(1) {
            a = m % 10;
            b += a;
            c = (double)m / 10;
            if(c < 10) {
                if(tmp >= 10) result = tmp + b + (int)c;
                if(tmp < 10) result = tmp + b + (int)c*10;
                self[result-1] = 0;
                break;
        }
            m = (int)c;
        }
    }
        for(int i=0; i<10000; i++) {
        if(self[i] != 0) printf("%d\n", i+1);
    }
}

3. 풀이

죄송하지만 함수는 사용하지 않았어요..

 

int self[15000];

 

- 먼저 셀프넘버인지 구분하기 위한 배열 self를 선언하였습니다.

 

- 배열 크기가 왜 10000을 넘는지는 나중에 설명하겠습니다.

 

for(int i=0; i<15000; i++) self[i] = i+1;

 

- 배열에 각 숫자를 넣어주었습니다. -> self[0] = 1, self[1] = 2, ... , self[14999] = 15000

 

- i+1인 이유는 배열은 0부터 시작하기 때문이고, 문제에서 주어진 값의 범위는 1부터 시작이기 때문입니다.

 

- 특별히 값을 넣어준 이유는 없고 임의대로 겹치지 않는 값을 넣어주셔도 됩니다.

 

- 저는 중복을 피하기 위해 임의로 i+1로 넣었습니다.

 

 for(int i=0; i<10000; i++) {

 

- i는 0부터 10000까지 반복하며 이는 문제에서 주어진 값의 범위 1부터 10000까지로 생각하시면 됩니다.

 

int m = i+1;

 

- m은 1부터 10000까지 넣어 줄 변수입니다.

 

int tmp = m;

 

- 나중에 계산에서 m이 수정되기 때문에 원본 m을 tmp에 저장시켜줍니다.

 

int a = 0, b = 0, result = 0; double c = 0;

 

- 계산을 마치고 다음 수로 넘어갔을 때, 다시 처음부터 계산하기 때문에 전부 초기화해줍니다.

 

while(1) {

 

- break가 나올때까지 무한루프

 

a = m % 10;

 

- m % 10 은 각 자릿수를 구하기 위함입낟. 맨 오른쪽 수를 a에 저장해줍니다.

 

b += a;

 

- b는 각 자릿수의 합을 구해줍니다.

 

c = (double)m / 10;

 

- c는 다음 자릿수를 구하기 위해 m을 10으로 나눠줍니다.

 

( ex : m = 9999 , a = 9 , b = 9 , c = 999.9 )

 

- 이 때 m에 double을 선언한 까닭은 m을 10으로 나눠줄 경우 소숫점이 발생하고, 이 때 간섭을 받지 않기 위함입니다.

 

- 이 때문에 c 또한 처음부터 double을 선언해주었습니다.

 

if(c < 10) {

 

- c가 10보다 작을 경우, 즉, 자릿수가 하나만 남았을 경우(= 모든 자릿수를 구했을 경우)입니다.

 

if(tmp >= 10) result = tmp + b + (int)c;

 

- 처음의 m 값이 10보다 클 경우, tmp + b(맨 앞자릿수를 제외한 자릿수의 합) + (int)c (남은 한 자릿수)를 합해줍니다.

 

- 즉 result는 문제에서 생성자입니다.

 

- c에 int를 선언해주는 이유도 소숫점을 없애주기 위함입니다.

 

 if(tmp < 10) result = tmp + b + (int)c*10;

 

- tmp가 10보다 작을 경우입니다.

 

- tmp 와 b(=0), c에다 10을 곱해줍니다! (-> 1을 10으로 나누면 0.1이고, 이를 다시 10으로 곱해줘야 1이기 때문)

 

self[result-1] = 0;

 

- result-1을 해준 이유는 배열이 0부터 시작이고, 문제에서 주어진 범위는 1부터 시작이기 때문입니다!!

 

- 위 코드는 생성자를 구분해주는 것입니다.

 

- 즉, 2가 생성자라면, self[1] = 0으로 저장하여 나중에 0이 아닌 값을 self넘버로 구분하면 됩니다.

 

- 여기서 self[15000] 을 선언해준 이유가 나옵니다.

 

- m = 9999 일 경우, 계산을 통해 result = 10035가 나오게됩니다.

 

- 만약 self[10000]으로 선언해주었을 경우 배열의 크기를 넘었기 때문에 참조오류가 발생합니다.

 

break;

 

- 계산식을 빠져 나가고 다음 수로 넘어갑니다.

 

m = (int)c;

 

- if(c < 10)  조건을 만족하지 않는 경우, m에서 10을 나눠준 값 c를 m으로 저장해줍니다.

 

- ex : m = 9999 , c = 999.9 , m = (int) c = 999

 

for(int i=0; i<10000; i++) {
        if(self[i] != 0) printf("%d\n", i+1);

 

- 0부터 9999까지, self[i] 가 0이 아닐 경우 ( self 넘버일 경우 ) 그 수를 출력해줍니다.

 

- ex : self[0] 의 값은 1일테며 i+1인 1을 출력합니다.

 

 

 

코린이라 코드가 참 난잡하네요. 그래도 스스로 힘으로 풀려고 노력한 결과라고 생각하고 아량을 베풀어 주세요 ㅠ.