[백준 1037] 약수 C++

약수

티어 : Bronze 1
알고리즘 분류 : 수학, 정수론

---

약수 짝끼리의 곱은 N이 된다는 성질을 이용했다.

e.g., 8의 약수 = {1, 2, 4, 8}

         → 1 * 8 = 8

         → 2 * 4 = 8

따라서 진짜 약수를 모두 벡터에 담은 후 벡터를 오름차순 정렬하면 벡터의 첫 번째 요소와 마지막 요소는 약수 짝이 될 것이므로 두 값을 곱한 값이 N이 된다.

Algorithm

1. 입력받은 진짜 약수를 모두 vector에 담음
2. 벡터를 오름차순 정렬해 약수끼리 짝이 맞을 수 있도록 함
3. 벡터의 첫 번째 요소와 마지막 요소를 곱함

 

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt; // N의 진짜 약수의 개수
vector <int> v; // N의 진짜 약수
int N;

void input(){
    cin >> cnt;
    for(int i=0;i<cnt;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
}

void solution(){
    // 벡터 오름차순 정렬
    sort(v.begin(), v.end());
    // 벡터의 처음 값과 마지막 값 곱함
    N = v[0] * v[v.size()-1];
}

void output(){
    cout << N;
}

int main(void){
    input();
    solution();
    output();
    return 0;
}

메모리: 2020 KB
시간: 0 ms