Codeforces #1514A Perfectly Imperfect Array

문제

https://codeforces.com/problemset/problem/1514/A

걸린 시간

00 : 19 : 25

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto& i : a) cin >> i;
        auto solve = [&]() -> bool{
            for(int i = 0; i < n; i++){
                bool perfect = false;
                for(int j = 1; j <= 100; j++){
                    if(j*j == a[i]) perfect = true;
                }
                if(!perfect) return true;
            }
            return false;
        };
        cout << (solve() ? "YES" : "NO") << "\n";
    }
    return 0;
}

완전 제곱수, perfect square 용어를 알지 못해 문제를 오래 읽었다. 완전 제곱수에 대해 잘 모르지만 예제를 몇개 풀어보니 완전 제곱수끼리의 곱은 항상 완전 제곱수임을 알 수 있었다. 집합 a 의 부분집합 b 의 모든 원소 곱이 하나라도 완전 제곱수가 아니라면 YES, 모두 완전 제곱수라면 NO 를 출력해야 하므로 모든 수가 완전 제곱수인지만 확인해주면 된다.