[백준/C++] 28421번: 곱하기와 쿼리

문제

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

28421번: 곱하기와 쿼리

---

문제 요약

길이 가 N인 수열 A가 주어졌을 때, 다음 질의를 수행하는 프로그램을 작성한다.

 

1 x: 수열에서 두 수를 골라 x를 만들 수 있으면 1, 없으면 0을 출력한다.

만약, 같은 수를 선택하는 경우, 2개가 필요하다.

(  0 ≤ x ≤ 100,000,000)

 

2 i:  A의 i번째 수를 0으로 변경한다.

 

+ 수열에 존재하는 수는 1 ~ 10000이다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, Q;

vector<int> A;

int arr[10001]; // arr[i]: A에 존재하는 i의 개수

int main() {
    // 입출력 시간 단축
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> Q;

    // 수열 입력
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        A.push_back(num);
        arr[num]++;
    }

    // 쿼리 입력
    for (int i = 0; i < Q; i++) {
        int q, num;
        cin >> q >> num;

        // 명령 1
        if (q == 1) {
            int flag = false;

            // 0을 만들 수 있는지 탐색하는 경우를 따로 탐색
            // 0은 1개만 있어도 만들 수 있다. (단, 2개를 골라야 함으로 수열의 길이가 2이상)
            if (num == 0 && arr[0] > 0 && N > 1) {
                flag = true; 
            }
            else {
                // 1 ~ 10000 중 수열 A에 존재하는 num의 약수 탐색
                for (int i = 1; i <= 10000; i++) {
                    if (num % i == 0 && arr[i] > 0) {
                        // 제곱 수인 경우 
                        if (i * i == num) {
                            if (arr[i] >= 2) { // 서로 다른 수 2개를 조합하므로, 2개 필요
                                flag = true;
                            }
                        }
                        else {
                            // i에 곱해서 num을 만드는 데 필요한 수 num / i가 A에 존재하는지 확인 (인덱스를 벗어나는 경우 주의)
                            if (10001 > num / i && arr[num / i] > 0) { 
                                flag = true;
                            }
                        }
                    }
                }
            }

            if (flag) {
                cout << 1 << "\n";
            }
            else {
                cout << 0 << "\n";
            }
        }

        // 명령 2
        else {
            // 개수 변경
            arr[A[num - 1]]--;
            arr[0]++;
            // 수열 변경
            A[num - 1] = 0;
        }
    }

    return 0;
}

---

코드 설명

수열 A에서 서로 다른 2개를 선택하는 모든 경우의 수를 탐색한다면 시간복잡도가 O(N^2)으로 시간 초과가 발생한다.

 

처음에는 수열 A를 오름차순으로 정렬하고, 투포인터 방식을 이용하여 O(N)에 해결하려고 했지만, i번째 원소를 0으로 바꾸는 쿼리 2 과정에서 순서를 찾기 어려워 다른 방법을 이용했다.

 

따라서 수열 A에 x가 들어 있는 개수를 저장하는 배열 arr[x]를 이용한 완전 탐색으로 문제를 해결한다.

 

수열 A에서 두 수를 골라 배수로 만들 수 있는지 확인할 숫자를 num이라고 한다면, 1부터 10000까지 수(i) 중 어떤 수와 곱해서 num을 만들 수 있는 수 (즉, num의 약수)가 수열에 존재하는지를 arr를 통해 O(1)에 확인한다.

 

+ 제곱으로 num이 되는 경우, 같은 수가 2개 필요하므로 따로 처리한다.

+ 0은 1개만 있으면 어떤 수를 곱해도 0이므로, num이 0인 경우를 따로 처리한다.