[C++] 백준 1037 : 약수

 

문제에서 주어진 조건은 다음과 같다.

• N이 되기 위한 조건 주어지는 진짜 약수들의 배수이다.
• N은 주어진 진짜 약수들과 같은 수가 아니다.
• 진짜 약수들은 1과 N을 제외한 수이다.

 

예를 들어, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24인데, 문제 조건에 따라 1과 24를 제외하면 진짜 약수인 2, 3, 4, 6, 8, 12가 남는다.

문제에서는 진짜 약수를 보고 N을 찾아야 하는데, 진짜 약수의 최솟값과 최댓값을 곱하면 24가 나온다는 것을 알 수 있다.

 

따라서 주어지는 약수들을 배열로 먼저 받고 이들을 오름차순 정렬한 다음, 최솟값과 최댓값을 곱하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;


int main() {
	int n; cin >> n;
	int arr[51];

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	
	sort(arr, arr+n);

	int ans = arr[0] * arr[n - 1];
	cout << ans;
}