[Baekjoon] 약수(BOJ 1037)

👀 문제 설명

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

2

4 2

 

예제 출력 1

8

 

✍🏻풀이

진짜 약수의 개수가 홀수일 때와 짝수일 때로 나눠서 생각했다.

 

1) 홀수일 때

정가운데 수를 가져와서 제곱하면 N이 나온다.

 

2) 짝수일 때

가운데 두 수를 가져와서 곱하면 N이 나온다.

 

이렇게 했는데 미처 생각하지 못한 부분이 있었다! N의 진짜 약수를 입력받을 때 작은 수부터 오름차순으로 입력받는 게 아니라, 무작위로 입력받을 수 있기 때문에 제대로 된 N 값이 나오지 않을 수 있다는 것이었다 ◡̈

그래서 위의 방법으로 N을 구하기 전에, 입력받은 진짜 약수들을 sort를 통해 오름차순으로 정렬해주었다!

 

필요한 변수

int n : 진짜 약수의 개수

vector<int> aliquot : 입력받은 진짜 약수들을 이 벡터에 넣는다.

 

알고리즘

1. 진짜 약수의 개수를 입력받는다.

2. 입력받은 진짜 약수의 개수만큼 for문을 돌려 진짜 약수들을 입력받고, aliquot 벡터에 넣는다.

3. aliquot 벡터를 오름차순으로 정렬한다. 

4-1. 진짜 약수의 개수가 홀수일 경우, 가운데 값을 가져와 제곱하여 return한다.

4-2. 진짜 약수의 개수가 짝수일 경우, 가운데 두 값을 가져와 곱하여 return한다.

 

코드

//
//  BOJ_1037.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/05/29.
//  Copyright © 2020 조수민. All rights reserved.
//
//  약수(https://www.acmicpc.net/problem/1037)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> aliquot;

int getNumber()
{
    if (aliquot.size() % 2 == 0) // 진짜 약수의 개수가 짝수일 때
    {
        int num1Index = aliquot.size() / 2 - 1;
        int num2Index = num1Index + 1;
        int num1 = aliquot[num1Index];
        int num2 = aliquot[num2Index];
        
        return num1 * num2;
    }
    else // 진짜 약수의 개수가 홀수일 때
    {
        int mediumIndex = aliquot.size() / 2;
        int squareNum = aliquot[mediumIndex];
        
        return squareNum * squareNum;
    }
}


int main(void)
{
    // 입력 받기
    cin >> n;
    aliquot.resize(n);
    
    for (int i = 0; i < aliquot.size(); i++)
        cin >> aliquot[i];
    // 입력 받기 끝
    // 벡터 정렬
    sort(aliquot.begin(), aliquot.end());

    // 출력
    cout << getNumber() << endl;
    
    return 0;
}