[백준] 4673 셀프넘버(C#)

문제

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

4673번: 셀프 넘버

처음에 셀프 넘버를 이해하지 못해서.. 모든 수가 셀프 넘버 아님? 이해가 안되네.. 라며 머리를 뜯고 있었는데, 뤼튼이가 알려줬다.

어머! 얘. 내가 알려줄게, 셀프 넘버에 대해서 헷갈려하는 거 같은데, 셀프 넘버에 대해서 설명해 줄게. 셀프 넘버는 생성자가 없는 숫자야. 즉, 어떤 n에 대해 d(n)으로 표현될 수 없는 숫자지. 예를 들어서, 20이 셀프 넘버인 이유는 20을 만들 수 있는 d(n)이 없기 때문이야. 20 + 2 + 0 = 22라는 건 맞지만, 이건 22가 20을 생성자로 갖는다는 걸 의미해. 즉, 22는 셀프 넘버가 아니지. 셀프 넘버는 반대로, 20을 만들 수 있는 그런 n이 없어야 해. 다시 말해서, 20을 n과 n의 각 자리수를 더한 결과로 만들어낼 수 있는 그런 n이 없다는 거야. 이해가 갔어? 셀프 넘버는 생성자가 없는 숫자라는 거야. 그래서 20은 셀프 넘버가 맞고, 22는 20의 생성자를 갖기 때문에 셀프 넘버가 아니지.

코드

using System;
using System.Text;
using System.Collections.Generic;

namespace baekjoon
{
    class Algorithm
    {
        static void Main(string[] str)
        {
            // int[] arr = new int[10000+1];
            HashSet<int> arr = new HashSet<int>();
            
            int num = 1;
            
            while(num <= 10000)
            {
                int total = 0;
                total += num;
                
                int mil = num / 10000;
                int tho = (num % 10000) / 1000;
                int hun = (num % 1000) / 100;
                int ten = (num % 100) / 10;
                int one = num % 10;
                
                total += mil + tho + hun + ten + one;
                
                if(total <= 10000)
                {
                    arr.Add(total);
                }
                
                num++;
            }
            
            for(int i = 1; i <= 10000; i++)
            {
                if(!arr.Contains(i))
                {
                    Console.WriteLine(i);
                }
            }
        }
    }
}

고민

1. 1 ~ 10000까지의 수에대해 계산

2. 값이 나오면 배열에 담고

3. 배열을 순회하여 값이 '0'이면 셀프넘버이므로 출력

 

처음엔 배열을 사용했으나 Index 에러가 발생하는 것을 보고.. Hash Set을 사용해봤다.

 

while문으로 모든 수를 구한 다음, for문에서 hash Set에 존재하지 않는 숫자들 즉, 셀프넘버를 출력했다.

 

다른 분들은 1의 자리부터 1000자리까지 구하는 로직을 어떻게 작성했는지 궁금해진 문제였다. 그리고 어떤 자료구조를 사용했는지도!