1037번 약수

문제링크 : www.acmicpc.net/problem/1037

1037번: 약수

 

 

방법1. 주어진 약수 중 가장 작은 값과 가장 큰 값을 곱함

   -> 루트N을 제외한 모든 약수는 둘 씩 짝지어 두 수의 곱이 N이 되도록 할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int N = 0;
	cin >> N;
	vector<int>numbers;
	for (int i = 0; i < N; i++) {
		int n = 0;
		cin >> n;
		numbers.push_back(n);
	}
    //오름차순으로 정렬
	sort(numbers.begin(), numbers.end());
    //가장 작은값과 가장 큰값의 곱
	cout << numbers[0] * numbers[int(numbers.size() - 1)];
	return 0;
}

 

 

방법2. 최소공배수 구하기

  -> 단, 이 경우는 고려해야할 경우가 많습니다.

       ex) 입력이 1개만 주어졌을 경우 -> 루트N의 약수가 주어진 경우

       ex) 최소공배수 값이 입력으로 주어진 약수 값과 같은 경우

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int gcd(int a, int b) {
	while (b != 0) {
		int n = a % b;
		a = b;
		b = n;
	}
	return a;
}
int main() {
	int N = 0;
	cin >> N;
	vector<int> numbers;
	for (int i = 0; i < N; i++) {
		int n = 0;
		cin >> n;
		numbers.push_back(n);
	}
	sort(numbers.begin(), numbers.end());
	if (numbers.size() == 1) {
		cout << numbers[0] * numbers[0];
	}
	else {
		int gcd_n = (numbers[0] * numbers[1]) / gcd(numbers[0], numbers[1]);
		for (int i = 2; i < N; i++) {
			gcd_n = (gcd_n*numbers[i]) / gcd(gcd_n, numbers[i]);
		}
		cout << ((gcd_n == numbers[int(numbers.size() - 1)]) ? gcd_n * numbers[0] : gcd_n);
	}
	return 0;
}

이 외에도 고려해야할 경우들이 많기때문에 코드도 길고 복잡해질 것입니다.(위의 코드는 틀렸어요....) 때문에 간단하고 명확한 1번 방법으로 진행해야 할 것 같습니다.