[백준] 1037. 약수

문제

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

풀이

혹시 아무리 생각해도 자신의 아이디어가 맞는 것 같은데 틀리게 나온다면 문제를 다시 한번 잘 보자. 이 문제에서 주는 데이터는 약수가 크기 순으로 정렬 된다는 보장이 없다! 즉 8의 약수에 대한 데이터가 아래와 같이 주어질 수 도 있다는 것이다. 따라서 입력을 저장한 다음에 저장한 배열을 정렬해주던가 해야한다.

2

4 2

그 다음부터는 아마 여러분이 생각한대로 일텐데, 어떤 수는 기본적으로 가장 작은 약수 * 가장 큰 약수로 구할 수 있다. 혹시 이 내용을 모르고 있다면 아마 고등학교때 배운 수학 내용을 잊어버린 것일텐데, 간단히 몇개의 수만 분석해도 깨달을 수 있을 것이다.

위의 예시인 8을 보자. 8의 약수는 1 2 4 8 이다. 따라서 1 * 8 = 8 혹은 2 * 4 = 8 로 알 수 있다.

이번에는 16을 보자. 16의 약수는 1 2 4 8 16 이다. 이 때는 1 * 16 = 16, 2 * 8 = 16, 4 * 4 = 16 으로 알 수 있다.

마지막으로 24를 보자. 24의 약수는 1 2 3 4 6 8 12 24 이다. 역시 1 * 24, 2 * 12, 3 * 8, 4 * 6 으로 알 수 있다. 

이처럼 가운데를 기준으로 나눠서 대칭되는 왼쪽과 오른쪽을 곱하면 그 수가 나오게 된다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>

using namespace std;

int main(){
    
    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);

    int N; cin >> N;
    long long nn[51] = { 0, };
    for(int i = 0; i < N; i++){
        cin >> nn[i];
    }
    sort(nn, nn + N);

    cout << nn[0] * nn[N - 1];
    return 0;
}