문제
- 문제 링크
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$같은 자료구조를 써먹어도 되겠다.
이제 삽질하기 쉬운 여러 케이스들을 잘 고려했는지만 확인하자.
전체 코드
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 37 38 39 40 41 42 | #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; } } } | cs |
comment
끝
'Problem Solving > Baekjoon Online Judge (Gold)' 카테고리의 다른 글
백준 28707 - 배열 정렬 (C++) (0) | 2023.08.15 |
---|---|
백준 23792 - K번째 음식 찾기 2 (C++) (0) | 2023.08.09 |
백준 28426 - 더하기와 나누기 (C++) (0) | 2023.08.04 |
백준 28422 - XOR 카드 게임 (C++) (0) | 2023.07.31 |
백준 28333 - 화이트 칼라 (C++) (0) | 2023.07.20 |