Codeforces Round 560 Div. 3 D Almost All Divisors

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<string>
#include <cstring> //memset
using namespace std;
typedef long long ll;
 
int main(void)
{
    int cases;
    cin >> cases;
    while (cases--) {
        int n;
        cin >> n;
        vector<ll> arr;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            arr.push_back(a);
        }
        sort(arr.begin(), arr.end());
        ll ans = arr[0] * arr[n - 1];
        int locate=0;
        bool Check = true;
        for (ll i = 2; i <=arr[n - 1]; i++) {
            ll tmp = ans % i;
            if (tmp == 0) {
                if (arr[locate] != i) {
                    Check = false;
                    break;
                }
                else
                    locate++;
            }
        }
        if (!Check)
            cout << -1 << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

출처:https://codeforces.com/contest/1165/problem/D

시간복잡도 때문에 별 헛짓거리를 다했네요....ㅋㅋㅋㅋ 

1 ->17 인경우 289가 나와야 하고  2,->5 6 인경우는 -1 

3->2 3 5는 -1 이런 예제들을 이용하면 쉽게 풀 수 있습니다. 문제는 시간복잡도를 해결하는 것이였는데요... 

만약 예제입력이 최적이라면 

1.입력의 답은 정렬했을때 가장 작은수*가장 큰수 인 것을 이용하고,

2.배열이 정렬된 것을 이용해서 풀 수 있는 문제였습니다.

3.변수형은 long long을 써주셔야 됩니다!

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<string>
#include <cstring> //memset
using namespace std;
typedef long long ll;
 
int main(void)
{
    int cases;
    cin >> cases;
    while (cases--) {
        int n;
        cin >> n;
        vector<ll> arr;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            arr.push_back(a);
        }
        sort(arr.begin(), arr.end());
        ll ans = arr[0] * arr[n - 1];
        bool Check = true;
        for (ll i = 2; i <=arr[n - 1]; i++) {
            ll tmp = ans % i;
            if (std::find(arr.begin(), arr.end(), i) != arr.end()) {
                if (tmp != 0) {
                    Check = false;
                    break;
                }
            }
            if ( tmp== 0) {
                if (std::find(arr.begin(), arr.end(), i) == arr.end()) {
                    Check = false;
                    break;
                }
            }
        }
        if (!Check)
            cout << -1 << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

이런 식으로 계속 코드를 왔다갔다하면서 바꿔봤는데, find를 써주니까 계속 당연히 터지는 거였습니다만, 머리가 안돌아가서 계속

find로 풀려고했습니다...

결국 이미 정렬을 했다는 것을 이용해서 코드를 바꿔줘서 AC를 받았네요.