[C#] 백준 9506 약수들의 합

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

 

자신을 제외한 약수를 합한 값을 완전수 라고 하는데 이를 완전수일 경우 해당 약수의 계산식을, 아니면 is NOT perfect.를 출력하는 문제이다.

 

약수임을 판단

 

약수의 경우 나눴을 때 나머지가 0이 되어야 하며, 12라고 가정하면 1, 12, 3, 4, 6, 6 이렇게 된다. 그런데 1 3 4 6 12를 다 구할때 까지 12번 반복하는 것 보다, 반으로 나눠서 1을 구하면 12도 자동으로 딸려오고, 3을 구하면 4도 자동으로 딸려오기 때문에 제곱근으로 반 나눠서 반복하면 반복하는 시간을 좀 더 효율적으로 줄일 수 있다.

 

Math.Sqrt()를 이용해 입력한 값의 제곱근을 반복하여 i와 입력값 / i 를 list에 담으면된다.

 

  static List<int> Divisor(int num)
  {
      List<int> divisors = new List<int>();

      for(int i = 1;  i <= Math.Sqrt(num); i++)
      {
          if(num % i == 0)
          {
              divisors.Add(i);
              // 중복 방지 && 자기 자신 방지
              if(i != num / i && num != num / i)
              {
                  divisors.Add(num / i);
              }
          }

      }

      divisors.Sort();

      return divisors;
  }

 

완전수인지 판단

list를 반복해서 더하는 방식이 있지만, 이미 foreach문으로 list를 반복하여 출력하고 있기 때문에 이중 반복문 보단, list의 합을 구해주는 list.Sum() 함수를 통해 list의 모든 합을 구하여 출력하면 된다.

 

 foreach (int num in list)
 {
     divisor = Divisor(num);

     if(divisor.Sum() == num)
     {
         string result = $"{num} = {string.Join(" + ", divisor)}";
         Console.WriteLine(result);
     }
     else
     {
         Console.WriteLine($"{num} is NOT perfect.");
     }
 }

 

 

전체 코드

using System;

class Program
{
    static void Main(string[] args)
    {
        List<int> list = new List<int>();
        List<int> divisor = new List<int>();

        list = Inputs();

        foreach (int num in list)
        {
            divisor = Divisor(num);

            if(divisor.Sum() == num)
            {
                string result = $"{num} = {string.Join(" + ", divisor)}";
                Console.WriteLine(result);
            }
            else
            {
                Console.WriteLine($"{num} is NOT perfect.");
            }
        }


    }

    static List<int> Inputs()
    {
        List<int> list = new List<int>();

        while (true)
        {
            int N = int.Parse(Console.ReadLine());
            if(N == -1)
                return list;

            list.Add(N);
        }
    }

    static List<int> Divisor(int num)
    {
        List<int> divisors = new List<int>();

        for(int i = 1;  i <= Math.Sqrt(num); i++)
        {
            if(num % i == 0)
            {
                divisors.Add(i);
                // 중복 방지 && 자기 자신 방지
                if(i != num / i && num != num / i)
                {
                    divisors.Add(num / i);
                }
            }

        }

        divisors.Sort();

        return divisors;
    }
}