[C++] - 백준(Baekjoon) : 4673번 셀프넘버

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

4673번: 셀프 넘버

 

셀프넘버라는 개념을 이해하는데 조금 어려웠기 때문에 한번 설명해보자면,

(쉬운 문제라고 했었는데 조금 부끄러움)

 

셀프넘버는 어떤 정수와 그 수를 구성하고 있는 각 자릿수를 더해서 만들 수 있는 수가 아닌 숫자이다. (생성자가 없는 숫자)

- n은 d(n)의 생성자라고 한다. n을 통해 d(n)이라는 식 만들 수 있다는 의미이다.( d(n) = n )

- n = 1이면 1+1 = 2 ---> d(1) = 2 

- n = 2이면 2+2 = 4 ---> d(2) = 4

- n = 13이면 13+1+3 = 17 ---> d(13) = 17 

- n = 2534이면 2534+2+5+3+4 = 2548 ---> d(2534) = 2548 

- 이것처럼 2의 생성자는 1이고, 4의 생성자는 2, 17의 생성자는 13이다. 

 

우리는 이러한 생성자 n이 없는 숫자를 찾아야한다.  

- 예를 들면 1이나 3, 자기 자신과 각 자리수를 더해서 만들 수 없는 수를 찾아내면 된다 

- 없는 수를 찾는건 어려우니까 있는 수를 찾은 후에 이를 제외하고 출력해주면 된다. 

 

내가 작성한 코드 

#include <iostream>
#include <vector>
#define MAX 10001
using namespace std;

int dn(int n)
{
    int ans = n;
    do
    {
        ans += n % 10;
    } while ((n /= 10) != 0);
    return ans;
}

int main()
{
    vector<bool> a(MAX, false);
    for (int i = 0; i < MAX; i++)
    {
        a[dn(i)] = true;
    }

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

 

솔직하게 이실직고하자면 dn 함수를 구현하는데 있어서 좀 찾아봤다.

내가 처음 생각한 방법은 %1d로 끊어서 받아서 더하기 -> 입력이 없는데 도대체 뭘 입력받겠다는거야?

나누고 더하고, 나누고 더할건데 도대체 언제까지 더해야하는거지? -> 반복문 종료 조건을 헷갈림 

이거저거 하다가 너무 비효율적인 알고리즘이 만들어져서 이건 아니다 싶어서 다른 블로그 글을 참고했다.. 잠깐.. 

 

int dn(int n)
{
    int ans = n;
    do
    {
        ans += n % 10;
    } while ((n /= 10) != 0);
    return ans;
}

함수를 구현하도록 유도하는 문제였기 때문에 생성자를 확인하는 함수를 구현했다. 

각 수를 10으로 나눈 나머지를 ans에 더해서 자릿수를 더해주고, 조건문에서 n /= 10을 하면서 계속 나눠주었다.

그래서 나눴을 때 몫이 0이 될 때까지 반복되게 하였다. 

1의 자리 숫자일때도 작동되게 하려고 do while문을 작성해 한번은 작동하게 구현하였다. 

 

int main()
{
    vector<bool> a(MAX, false);
    for (int i = 0; i < MAX; i++)
    {
        a[dn(i)] = true;
    }

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

vector를 사용해서 bool 배열을 생성하고 a(MAX, false)를 해줌으로서 MAX의 길이만큼 false로 초기화해주었다.

☑️ vector<bool> a(MAX, false); 

: false로 초기화 된 MAX개의 원소를 가지는 vector a 생성. 

 

for문을 돌리면서 생성자가 있는 함수는 true로 만들어주고, 다시 for문을 돌리면서 생성자가 없는 함수를 출력시켜주었다.

 

 

알고리즘은 풀었지만 시간과 메모리 사용이 많다... 뭔가 불만족 

 

다시 고쳐본 코드  

#include <stdio.h>
#define MAX 10001
using namespace std;
int a[MAX];

int dn(int n)
{
    int ans = n;
    do
    {
        ans += n % 10;
    } while ((n /= 10) != 0);
    return ans;
}

int main()
{
    for (int i = 0; i < MAX; i++)
    {
        a[dn(i)] = 1;
        if (!a[i])
            printf("%d\n", i);
    }
}

뭐야.. c++에서 c로 바꾸니까 확 줄어들잖아?

이정도로 달라지는줄은 몰랐는데,,, 하면서 겸사겸사 for문도 두번 안쓰고 한번으로 줄었다. 

그리고 배열을 전역으로 선언해줘야 오류가 안난다. 왜 그런지는 아직 이해못했다. 메인에 선언하니까 무한루프에 걸리더라