[C++] 백준 1037번 - 약수

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

접근

1. 숫자들을 배열에 받는다
2. 배열을 작은수부터 차례대로 정렬
3. n의절반 + n의절반+1의 숫자를 곱한게 정답

이렇게 순서대로 코드를 짰다

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
using namespace std;

int main() {

    int n;
    scanf("%d", &n); //정답의 약수의 개수 1이랑 본인 제외 

    int num[50] = { 0, };

    for (int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
    }

    int len = n;
    int ans = 0;
    if (n == 1) {
        printf("%d", num[0] * num[0]);
    }
    else {
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (num[j] > num[j + 1]) {
                    swap(num[j], num[j + 1]);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (n % 2 == 0) {
                ans = num[n / 2 - 1] * num[n / 2];
            }
            else {
                ans = num[(n - 1) / 2]* num[(n - 1) / 2];
            }
        }
        printf("%d", ans);
        
    }
    return 0;
}

리뷰

일단 숫자를 배열에 받아서 정렬하기 전에 if문으로 n이 1일 경우를 먼저 처리했다 n=1일때는 어차피 숫자는 하나니까 굳이 정렬을 할 필요가 없기때문에 바로 정답을 출력해줬다

 

그리고 버블정렬로 정렬을했다.

 

그 다음으로 n이 짝수일때, n이 홀수일때를 나눠서 코드를 짰다

n이 홀수일때는 중앙값을 두번 곱하면 된다. 

 

홀수일때나 n이 1일때 등만 신경쓰면 어렵지 않았던것 같다

 

 

++

다른 사람들은 어떻게 풀었나 보는데 겁나 쉬웠군

나는 숫자를 정렬하고 짝수일때 홀수일때 나눴는데 결국은 맨앞과 맨뒤를 곱하기만 하면 되는것이다

2 3 4 6 8 12 

이렇게 있으면 난 4와 6을 그러니까 제일 붙어있는 쟤네를 곱하는 방식을 썼는데 4,6을 곱해도 되고 3,8을 곱해되고 2,12를 곱해도 된다 이건 알고 있었는데 생각해보니 난 어려운 방법을 쓴것 같다 맨앞과 맨뒤를 곱하면 제일 간단하니ㅏ까!!!

 

max_element라는함수를 알게되었다 이 함수는 특정 범위 내에서 가장 큰요소를 가리키는 반복자를 반환하는 함수이다

int max = max_element(num.begin(), num.end());
int min = min_element(num.begin(), num.end());
cout << max * min;

이렇게 하면 굳이 정렬을 할 필요조차 없다

 

이런 방법도 잇엇군...

 

 

 

출처 

1037번: 약수 (acmicpc.net)