백준 문제풀이 - 1037 번

링크 -> https://www.acmicpc.net/problem/1037

1. 요약 및 풀이방법

어떤수 N의 약수중 1과 자기자신을 제외한 진짜 약수들이 주어질 때, 어떤수 N을 구하는 문제이다.
진짜약수 리스트를 정렬하여 진짜 약수 중, 가장 큰 값과 작은값의 곱으로 문제를 풀었다.

2. Code

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

std::vector<unsigned int> g_divisors;
unsigned int g_answer;

void input()
{
    int num_of_divisor;
    std::cin >> num_of_divisor;
    g_divisors.reserve(num_of_divisor);
    for (int i = 0; i < num_of_divisor; i++)
    {
        int tmp;
        std::cin >> tmp;
        g_divisors.push_back(tmp);
    }
}

void pre_processing()
{
    std::sort(g_divisors.begin(), g_divisors.end());
    std::reverse(g_divisors.begin(), g_divisors.end());
}

void solution()
{
    g_answer = *g_divisors.begin() * *(--g_divisors.end());
}

void print()
{
    std::cout << g_answer << std::endl;
}

int main()
{
    input();
    pre_processing();
    solution();
    print();
}

3. 학습 내용

처음에 풀이 방법을 잘못 생각하고
'가장 큰' 진짜약수의 n배수를 구하고,
그 n배수가 뒤의 진짜 약수들로 전부 나누어떨어지는지 확인하는 방법으로 코드를 작성했다.
틀린 예로,
진짜약수가 3, 9 인 경우 어떤수 N은 27이다.
하지만 9의 2배수인 18은 다른 진짜약수 3으로 나누어떨어지기 때문에 18이 나왔다.

다시 생각해보니 간단하게 가장 큰 진짜약수와, 가장 작은 진짜약수를 곱하면 풀리는 문제였다.

4. 결과