[C#/BOJ] 1037번: 약수

1) 문제 

1037번: 약수

---

2) 코드 

using System;
using System.IO;

class Multi
{
    static void Main()
    {
        int count = Int32.Parse(Console.ReadLine());

        //C#에서 숫자 리스트 입력받기 
        string input = Console.ReadLine();
        string[] factorsStr = input.Split(' ');
        int[] factors = new int[count]; 

        for(int i = 0; i<count; i++)
        {
            factors[i] = int.Parse(factorsStr[i]);
        }


        Array.Sort(factors);

        int n;
        

        n = factors[0] * factors[count - 1];


        Console.WriteLine(n);
    }
}

 

 

3) 해석 

📌 처음에는 최소공배수를 구하는건가 ..? 싶었지만 예시가 2,4로 주어진 경우 두 수의 최소공배수는 4인 반면 n의 값은 8이다 ! 

🔧 최소공배수는 아님 

 

📌 왜 굳이 개수를 주었을까 생각을 해보고 짝수일 때, 홀수일 때를 나눠서 생각해봤다. 

* 입력받은 숫자의 개수 = count
* 약수는 오름차순으로 정렬되어 있다고 가정 
count = 1일때 , 약수 : a →  n = a*2
count = 2일때 , 약수 : a b→  n = a*b
count = 3일때 , 약수 : a b c →  n = (b*2) or (a*c)
count = 4일때, 약수 a b c d → n = (a*d) or (b*c)
...
count = 6일때, 약수 a b c d e f → n = (a*f) or (b*e) or(c*d)

이렇게 정리해보니 홀수일 때는 가운데 수의 제곱, 짝수일 때는 양 끝 수의 곱이라는 사실이 나왔다. 

그런데 사실 홀수, 짝수 나눌 필요 없이 

 

count =k 일 때, 약수 a b c ... (k번째 수)  → n = (a*(k번째 수)) or (b*(k-1번째 수)) or (c*(k-2번째 수)) ... 

즉, 곱하는 두 수의 인덱스 합이 k!!! 

옛날 수열에서 배웠던 등비중항의 성질을 이용하면 된다 !! 

 

그래서 작성한 알고리즘은 

1) string형태로 입력받은 리스트 int형태 리스트로 저장

2) 오름차순 정렬

3) 등차중항의 성질 이용하여 index합이 count가 되는 수의 곱 반환 

 

끗 ~ 

브론즈1이라 C#으로도 구현하기 쉬운 문제였다