PS/10775.cpp at master · jwjin95/PS · GitHub

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAXN 100050

int G,P,ans=0;
int gi[MAXN];
int parent[MAXN];

int find(int x){
    if(x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}

void unite(int x, int y){
    x = find(x);
    parent[x] = find(y);
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> G >> P;

    for(int i=0 ; i<P ; i++) cin >> gi[i];
    for(int i=1 ; i<=G ; i++) parent[i] = i;

    // for(int i=1 ; i<=P ; i++) cout << parent[i];

    for(int i=0 ; i<P ; i++){
        int gate = find(gi[i]);
        // cout << gate;
        if(gate == 0) {
            // ans = i;
            break;
        }
        unite(gate, gate-1);
        ans++;

    }
    cout << ans;
}

// 이중 for문 이용 (시간초과)

//     for(int i=0 ; i<P ; i++){
//         bool docked = false;
//         for(int j=gi[i] ; j>0 ; j--){
//             if(!isUsed[j]){
//                 isUsed[j] = true;
//                 docked = true;
//                 break;
//             }
//         }
//         if(!docked){
//             ans = i;
//             break;
//         }


//     }

//     cout << ans;
// }