반응형

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

 

28421번: 곱하기와 쿼리

길이가 $N$인 수열 $A_1, A_2, A_3, \cdots, A_N$이 주어진다. 다음 질의를 수행하는 프로그램을 작성하시오. 1 $x$: 수열에서 서로 다른 두 수 $i$, $j$를 골라 $A_i$, $A_j$를 곱하여 $x$를 만들 수 있으면 $1$, 없

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수열을 저장할 arr[ N ] 배열을 선언합니다.

 

2. 각 수의 개수를 저장할 box[ 10001 ] 배열을 선언합니다.

 

3. 수열을 입력받고, 각 숫자들의 개수를 box 배열에 더해줍니다.

 

4. 쿼리를 입력받을 때마다 1부터 i * i <= x까지 for문을 돌면서 숫자의 존재를 box 배열을 통해 체크하고, 두 수를 곱해서 x를 만들 수 있다면 1을 아니라면 0을 출력합니다.

 

[ 소스코드 ]

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
 
using namespace std;
 
int N, Q;
int arr[100001];
int box[20001];
 
bool check(int x)
{
    int i = 1;
 
    if (N == 1) return false;
 
    if (x == 0) {
        if (box[0]) {
            return true;
        }
        else return false;
    }
 
    if (x > 10000) {
        i = x / 10000;
    }
 
    for (i; i * i <= x; i++) {
        if (box[i] && x % i == 0 && box[x / i]) {
            if (i * i == x && box[i] < 2) {
                continue;
            }
            return true;
        }
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        box[arr[i]]++;
    }
 
    for (int i = 0; i < Q; i++) {
        int cmd, x;
        cin >> cmd >> x;
 
        if (cmd == 1) {
 
            if (check(x)) {
                cout << 1;
            }
            else {
                cout << 0;
            }
 
            cout << '\n';
        }
        else {
            box[0]++;
            box[arr[x]]--;
            arr[x] = 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26

+ Recent posts

티스토리툴바