[c++] 백준 1037 - 약수(수학)

0. [c++] 백준

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

1. 풀이

이 문제는 낚시성이 짙은 문제였다.

밑의 소스코드를 보면 주석을 가한 부분이 있는데, 그 부분은 주어진 약수에서 소수만 구하는 알고리즘이다.

허나 이러한 알고리즘이 없어도 간단하게 문제를 풀 수 있다.

바로 입력을 오름차순으로 정렬하고, arr[0] * arr[N-1]을 해주면 바로 정답이 된다.

이렇게 되는 이유는,

위와 같은 이유로 인해, arr[0] * arr[N-1]은 우리가 찾는 결과값이 되는 것이다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include<iostream> #include<algorithm> #include<vector>   using namespace std;   typedef unsigned long long ull;   int arr[51]; int prime[101];   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       int N;     cin >> N;     for (int i = 0; i < N; i++) {         cin >> arr[i];     }     sort(arr, arr + N);     /*int ptr = 0;     for (int i = 0; i < N; i++) {         bool check = false;         for (int j = 0; j < ptr; j++) {             if (arr[i] % prime[j] == 0)                 check = true;         }         if (!check)             prime[ptr++] = arr[i];     }*/       cout << arr[N-1] * arr[0];          return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!