[BAEKJOON] 백준 4436: 엘프의 검 (C#)

문제 링크

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

 

 

문제

중간계에 살고있는 엘프 종족은 특정 숫자를 다른 숫자보다 중요하다고 믿는다. 따라서, 그들은 금속 n만큼을 이용해서 칼을 만들 때, 두께를 다음과 같은 규칙을 지키는 k로 한다면, 엄청나게 강력한 칼을 만들 수 있다고 믿는다.

음이 아닌 정수 n이 주어졌을 때, 다음과 같은 수열을 만들 수 있다.

n, 2n, 3n, 4n, ..., kn

이때의 수열에서, 0~9까지의 숫자가 한 번 이상 나타나는 가장 작은 k를 찾아야 한다.

리븐델의 영주 엘론드는 이 일을 대신해주는 프로그램을 만들려고 한다. 금속의 양 n이 주어졌을 때, 위의 규칙을 지키는 이상적인 두께 k를 구하는 프로그램을 작성하시오.

 

 

입력

한 줄에 하나씩 n이 주어진다. n은 1보다 크거나 같고, 200,000,000보다 작거나 같은 정수이다.

 

 

출력

각 입력에 대해, 0~9까지 숫자가 모두 등장하는 가장 작은 값 k를 출력한다.

 

 

 

통과한 답안

namespace _4436
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string input;

            while ((input = Console.ReadLine()) != null)
            {
                long n = long.Parse(input);
                HashSet<long> set = new HashSet<long>();

                long cnt = 0;
                while (set.Count < 10)
                {
                    cnt++;
                    long number = n * cnt;

                    while (number > 0)
                    {
                        set.Add(number % 10);
                        number /= 10;
                    }
                }

                Console.WriteLine(cnt);
            }
        }
    }
}

 

주어진 입력 값 n에 1부터 k를 곱하면서 그 숫자에 있는 모든 숫자들을 기록하는데,

그 기록에 0부터 9까지 모든 숫자가 채워지는 순간의 k값을 구하는 문제이다.

 

다시 말해서 n이 1로 주어지면,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10까지 왔을 때,

1부터 9까지는 1~9에, 0은 10의 0이 채워지므로 k는 10이 된다.

 

n이 10인 경우에는 처음에 1과 0이 있으므로,

그 뒤에 20, 30, 40, 50, 60, 70, 80, 90이 되어 k는 9가 된다.

 

n이 123456789인 경우에는 처음에 1부터 9가 있고,

246913578, 370370367로 k가 3이 된다.

 

즉, 이 문제는 HashSet을 이용하면 쉽게 해결할 수 있는 문제로

cnt를 0부터 시작해서 n에 cnt를 곱하면서 n의 숫자들을 HashSet에 저장한다.

이 HashSet의 count가 10이 되는 순간 0~9의 숫자들이 채워진 것으로

while문을 이중으로 이용해서 HashSet에 0~9의 숫자들을 집어넣는 최소의 cnt를 구했다.