반응형
https://www.acmicpc.net/problem/10775
문제해결 방법 : Union-Find
이문제에서 생각할것은 도킹을 할수 없는 상태가 잇다면 그다음 쿼리는 처리안해주고 끝난다는 것이다.
두번째로는 gi 번째 게이트에 도킹한다고 과정할때 gi는 1~gi 까지 도킹 할 수 있는 가능성있다.
그 다음 쿼리가 또 gi를 한다면 처음 쿼리는 1~g(i-1) 번째로 도킹을 해야한다.
그 다음 쿼리가 또 gi 를 한다면 1번째와 2번째는 1~g(i-1) 를 서로 다른 게이트에 도킹햇어야한다.
문제를 이제생각해본다면 현재 gi 번째 게이트에 도킹 가능성만 판별하면 된다.
비행기가 순서대로 들어오기 때문에 1~ i-1 번째는 도킹이 되었다고 가정한다면 find(i) 를 하였을 경우
0이 아닌값이 존재하는 것은 find(i)
Find 하엿을 경우 부모노드가 0이 아니라면 앞선 셋들을 어떻게든 배치하면 현재 i번째 게이트를 비울수 있다는것을 판별할 수 있음.
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
|
public class Main {
static int G;
static int P;
static int g[];
static int p[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
G = sc.nextInt();
P = sc.nextInt();
g = new int[G + 1];
p = new int[P];
Init();
int ans = 0;
for (int i = 0; i < P; i++) {
p[i] = sc.nextInt();
}
for (int i = 0; i < P; i++) {
int next = Find(p[i]);
if (next == 0) {
break;
} else {
++ans;
g[next] = next - 1;
}
}
System.out.println(ans);
}
public static int Find(int x) {
if (x == g[x]) {
return x;
}
int xx = Find(g[x]);
return g[x] = xx;
}
public static void Init() {
for (int i = 1; i <= G; i++)
g[i] = i;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형
'ProgramSoliving' 카테고리의 다른 글
백준 16933: java (0) | 2020.04.30 |
---|---|
백준 : 7682 (0) | 2020.04.15 |
백준 : 1637 (0) | 2020.04.15 |
백준 : 5213 JAVA (0) | 2020.03.17 |
백준 : 12886 (0) | 2020.03.15 |