백준 28421 - 곱하기와 쿼리 (C++)

문제

• 문제 링크

  
   BOJ 28421 - 곱하기와 쿼리 
  

• 문제 요약

$1$ $x$ : 수열에서 서로 다른 두 수 $A_i, A_j$를 곱하여 $x$를 만들 수 있으면 $1$, 없으면 $0$을 출력한다.

$2$ $i$ : $A_i$를 $0$으로 바꾼다.


길이 $N$의 수열과 위의 두 유형으로 이루어진 $q$개의 쿼리가 주어진다.
$1$번 쿼리가 주어질 때마다 그에 맞는 답을 출력하자.

• 제한

TL : $1.5$ sec, ML : $1024$ MB




$0 ≤ x ≤ 10^8$

$1 ≤ N ≤ 10^5$

$1 ≤ A_i ≤ 10^4$

$1 ≤ Q ≤ 5*10^3$

알고리즘 분류

• 수학(math)
• 정수론(number_theory)

풀이

$1$번 쿼리가 주어질 때마다 $x$를 인수 분해한다고 생각해보자.
이때 여러 인수 쌍들이 나올테고, 임의의 한 쌍이 수열에 모두 존재하는 경우가 있는지 판단하면 된다.
시간 복잡도는 문제의 착한 제한 범위로 인해 보장된다.

$A_i ≤ 10^4$임에 따라, $10,001$칸의 카운트 배열을 운용해 수들을 관리하자.
이 경우 $x ≤ 10^8$기 때문에, 배열 범위를 넘어선 접근이 일어나지 않도록 유의해야 한다.

아니면 아싸리 $std::map$같은 자료구조를 써먹어도 되겠다.

---

이제 삽질하기 쉬운 여러 케이스들을 잘 고려했는지만 확인하자.

$x == 0$일 때에 대해 제대로 처리$?$

임의의 $A_i$가 변경될 때, 카운트 배열에만 반영하는 것이 아니라 기존 수열에도 반영했는지$?$

임의의 인수 쌍이 서로 같을 때, 카운트 배열에 기록된 값이 $2$ 이상$?$

등등등...

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
 
    vector <int> V(n), C(10001);
    for (int& i : V)
        cin >> i, C[i]++;
 
    for (int o, x; q--;)
    {
        cin >> o >> x;
        if (o & 1)
        {
            if (!x)
            {
                cout << (C[0] && (C[0] > 1 || n - C[0] > 0)) << '\n';
                continue;
            }
 
            int flag{};
            for (int i(1); !flag && i * i <= x; i++)
                if (!(x % i) && x / i < 10001)
                {
                    int p(i), q(x / i);
                    if (C[p] && C[q])
                        flag = p ^ q ? 1 : C[p] > 1;
                }
 
            cout << flag << '\n';
        }
        else
        {
            C[V[--x]]--;
            C[0]++;
            V[x] = 0;
        }
    }
}

comment

끝