백준 알고리즘 1037번 : 약수 (C++)

#include<iostream>
using namespace std;
 
int main() {
    
    // https://www.acmicpc.net/problem/1037
    
    int n, temp;
    
    scanf("%d",&n);
    
    int p[50];
    
    for(int i=0; i<n; i++){
        scanf("%d",&p[i]);
    }
        
    for(int i=0; i<n; i++){
        for(int j=0; j<n-1; j++){
            if(p[j] > p[j+1]){
                temp = p[j];
                p[j] = p[j+1];
                p[j+1] = temp;
            }
        }
    }
    
    int result = p[0] * p[n-1];
    printf("%d", result);
    
}

 

이 문제는 솔직히 말하자면 아직 잘 이해를 못하겠다.

일단 '진짜 약수'라는 개념이 뭔지 잘 모르겠다.

 

아무튼, 이 문제는 사실상 답지를 보고 따라친거나 마찬가지인 문제가 되어버렸다.

 

내가 생각했던 해법 또한 약수들의 곱을 이용한 것이었지만, 답은 아니었던 것 같다.

'제일 작은 약수'와 '제일 큰 약수'의 곱이 정답이라고 한다.

 

입력되는 N개의 진짜 약수들이 정렬되어 들어올 것이란 보장이 없으므로 오름차순으로 정렬한 뒤

제일 작은 약수와 제일 큰 약수를 곱해주고 출력하면 된다.