[C++] 백준 1037 - 약수

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

예제 입력 1 

2
4 2

예제 출력 1 

8

예제 입력 2 

1
2

예제 출력 2 

4

예제 입력 3 

6
3 4 2 12 6 8

 

예제 출력 3 

24

예제 입력 4 

14
14 26456 2 28 13228 3307 7 23149 8 6614 46298 56 4 92596

예제 출력 4 

185192

 

문제 해석 

1. 약수의 개수가 주어진다.
   1. 그 약수의 개수는 자기자신과 1을 제외한 약수의 개수이다.
2. 약수가 무작위 순서대로 주어진다.
   1. 오름차순으로 깔끔하게 정렬한다.
   2. 그러면 젤 첫원소와 마지막 원소를 곱하면 우리가 찾으려는 N을 구할 수 있다.
3. 만약 약수의 개수가 1개 일 때
   1. 예를 들어 9,25 등등
      1. 그 약수를 제곱하면  N이 나온다.

코드

/*
약수 구하기
양수 A가 N의 진짜 약수가 되려면 N이 A의 배수이고, A가 1과 N이 아니어야한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

첫째줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 중복되지 않는다.
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int com(int i, int j)
{
    return i < j;
}
int main()
{
    int n, result;
    cin >> n;
    vector<int> num;
    for (int i = 0; i < n; i++)
    {
        int N;
        cin >> N;
        num.push_back(N);
    }
    //입력 받은 num을 오름차순으로 정렬
    sort(num.begin(), num.end(), com);
    if (num.size() != 1) //
    {
        result = num[0] * num[num.size() - 1];
    }
    else
    { //약수의 개수가 홀 수라면
        result = num[0] * num[0];
    }
    cout << result;
}

 

느낀 점

계산 복잡도와 adversary 전략이랑 관련이 있다고 해서 풀어봤는데 크게 못 느끼겠다.

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

1037번: 약수