이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 13372번 : 'Glass Bridge' 문제에 대한 풀이 코드와 해설을 다루고 있습니다.
문제의 난이도는 Solved.ac 기준 Platinum V에 해당하며, 풀이를 위해 세그먼트 트리에 대한 기본 이해가 필요합니다.
13372번 : Glass Bridge
영어를 간단히만 할 수 있으면 해석할 수 있는 문제입니다.
그림만 봐도 대충 감이 올텐데, 위와 같이 1~N번 사이의 번호를 반대편의 주어진 번호 순서대로 연결했을 때 발생하는 교차점의 개수를 구하는 문제입니다.
당연히 N이 10만 이하이므로 O(N^2) 알고리즘으로는 해결할 수 없는 문제입니다.
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
|
#include <cstdio>
#include <vector>
using namespace std;
void updateTree(vector<long long> &Tree, int Node, int Begin, int End, int Index) {
if(Index < Begin || Index > End) return;
if(Begin == End) {
Tree[Node] = 1;
return;
}
int Mid = (Begin + End)/2;
updateTree(Tree, Node*2, Begin, Mid, Index);
updateTree(Tree, Node*2+1, Mid+1, End, Index);
Tree[Node] = Tree[Node*2] + Tree[Node*2+1];
}
long long cntBigger(vector<long long> &Tree, int Node, int Begin, int End, int Left, int Right) {
if(Left > End || Right < Begin) return 0;
if(Left <= Begin && Right >= End) return Tree[Node];
int Mid = (Begin + End)/2;
return cntBigger(Tree, Node*2, Begin, Mid, Left, Right) + cntBigger(Tree, Node*2+1, Mid+1, End, Left, Right);
}
int main() {
int T, N, Value;
scanf("%d", &T);
for(int i=0; i<T; i++) {
long long Sum = 0;
vector<long long> Tree;
scanf("%d", &N);
Tree.resize((N+1)*4);
for(int i=1; i<=N; i++) {
scanf("%d", &Value);
Sum += cntBigger(Tree, 1, 1, N, Value+1, N);
updateTree(Tree, 1, 1, N, Value);
}
printf("%lld\n", Sum);
}
}
|
cs |
숫자들의 나열을 잘 생각해보면 쉽게 원리를 떠올릴 수 있습니다.
먼저 1에 대응되는 첫 번째 숫자인 4를 먼저 놓고, 그 다음 두 번째 숫자인 8을 놓고 보면 4보다 작은 수였을 경우 교차가 발생하였는데 4보다 큰 8이기 때문에 교차가 발생하지 않습니다.
이런 원리로 생각해보면 3번째 숫자인 1은, 4보다도 작고 8보다도 작으므로 2번의 교차가 발생합니다.
이렇게 1번째 수부터 트리에 대입하면서 i번째 수 A[i]보다 큰 A[1] ~ A[i-1]이 몇 개 있는지 세어주면 됩니다.
이것을 위와 같이 세그먼트 트리로 구현할 수 있습니다.
또한 위의 문제는 Inversion Counting Problem으로도 알려져 있으니 참고하면 좋을 것 같습니다.
13681번 : Bolhas e Baldes
Marcelo와 Carlos가 게임을 하는데, 번호가 세워진 병들을 나열하는 게임입니다.
번호는 무작위로 놓여있으며 입력으로 주어지고, 인접한 두 병의 위치를 바꿀 수 있습니다.
이 때 순서가 정렬되어 있는 (3과 4와 같은) 병들은 움직일 수 없습니다. (4와 3은 가능)
그래서 Marcelo부터 수행을 시작하고 마지막에 움직일 수 없는 사람이 진다고 할 때, 주어진 입력에 대해 이기는 사람을 맞추는 게임입니다.
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
|
#include <cstdio>
#include <vector>
using namespace std;
void updateTree(vector<long long> &Tree, int Node, int Begin, int End, int Index) {
if(Index < Begin || Index > End) return;
if(Begin == End) {
Tree[Node] = 1;
return;
}
int Mid = (Begin + End)/2;
updateTree(Tree, Node*2, Begin, Mid, Index);
updateTree(Tree, Node*2+1, Mid+1, End, Index);
Tree[Node] = Tree[Node*2] + Tree[Node*2+1];
}
long long cntBigger(vector<long long> &Tree, int Node, int Begin, int End, int Left, int Right) {
if(Left > End || Right < Begin) return 0;
if(Left <= Begin && Right >= End) return Tree[Node];
int Mid = (Begin + End)/2;
return cntBigger(Tree, Node*2, Begin, Mid, Left, Right) + cntBigger(Tree, Node*2+1, Mid+1, End, Left, Right);
}
int main() {
int N, Value;
while(1) {
long long Sum = 0;
vector<long long> Tree;
scanf("%d", &N);
if(!N) break;
Tree.resize((N+1)*4);
for(int i=1; i<=N; i++) {
scanf("%d", &Value);
Sum += cntBigger(Tree, 1, 1, N, Value+1, N);
updateTree(Tree, 1, 1, N, Value);
}
if(Sum%2) printf("Marcelo\n");
else printf("Carlos\n");
}
}
|
cs |
막상 문제를 풀어보면 놀랍도록 위의 문제와 같은데, 이것은 문제 자체가 버블 정렬의 swap 횟수를 묻고 있기 때문입니다.
따라서 어떤 수를 기준으로 그 수보다 뒤에 더 작은 수가 몇 개나 있는지가 정렬의 기준이 되므로, 이것은 결국 정렬된 데이터와 주어진 데이터를 같은 번호끼리 연결했을 때 발생하는 교차점의 수를 묻는 것과 같습니다.
제출해보면 역시 정답을 인정받을 수 있습니다.
5847번 : Milk Scheduling
문제를 해석해보면 각 소마다 milking 하는데 걸리는 시간이 다르고 이들이 T[i]로 주어지며, 특정 소들에게는 반드시 어떤 다른 소보다 먼저 milking 해야 하는 순서가 있다고 할 때 이들을 모두 milking 하는데 걸리는 최소 시간을 구하는 문제입니다.
선후 연결관계가 없으면 다른 소들과 동시에 milking을 진행할 수 있으므로, 결국 연결 시간이 가장 긴 부분을 찾아 그 시간을 구하면 됩니다.
이것은 결국 시간을 간선으로, 소들을 노드로 생각했을 때 가장 긴 그래프를 찾는 위상정렬 문제로 변형시켜서 생각할 수 있습니다.
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
|
#include <cstdio>
#include <vector>
#include <queue>
#define MAX 10005
using namespace std;
int Degree[MAX], Time[MAX];
long long Sum[MAX];
vector<int> Node[MAX];
queue<int> Queue;
int main() {
int N, M, X, Y, Pop, Next;
long long Max = 0;
scanf("%d %d", &N, &M);
for(int i=1; i<=N; i++) scanf("%d", &Time[i]);
for(int i=1; i<=M; i++) {
scanf("%d %d", &X, &Y);
Node[X].push_back(Y);
Degree[Y]++;
}
for(int i=1; i<=N; i++)
if(!Degree[i]) {
Queue.push(i);
Sum[i] = Time[i];
}
while(!Queue.empty()) {
Pop = Queue.front();
Queue.pop();
for(int i=0; i<Node[Pop].size(); i++) {
Next = Node[Pop][i];
if(Sum[Pop]+(long long)Time[Next] > Sum[Next])
Sum[Next] = Sum[Pop] + (long long)Time[Next];
Degree[Next]--;
if(!Degree[Next]) Queue.push(Next);
}
}
for(int i=1; i<=N; i++) if(Sum[i] > Max) Max = Sum[i];
printf("%lld", Max);
}
|
cs |
Degree는 선행 노드들에 의해 연결되어 있는 간선의 수를 저장하고, Time은 각 milking에 소요되는 시간, 그리고 Node[x] = y는 x에서 y로 노드가 연결되어 있음을 의미합니다.
변수 선언만 위와 같이 해주면 나머지는 쉽게 해결이 되는데, 큐에다가 선행 노드가 없는 것들부터 처리하면서 각 노드를 기준으로 시간을 Sum에 저장하여 그들 중 가장 큰 Sum을 답으로 출력해주면 됩니다.
제출해보면 16ms 시간에 정답을 인정받을 수 있습니다.
'알고리즘 > 백준(BOJ) 문제풀이' 카테고리의 다른 글
[C++ 백준 풀이] 2699번 : 격자점 컨벡스헐 / 6194번 : Building the Moat / 10903번 : Wall construction (0) | 2021.12.15 |
---|---|
[C++ 백준 풀이][Platinum] 1708번 : 볼록 껍질 (Convex Hull 알고리즘) (1) | 2021.12.14 |
[C++ 백준 풀이] 1849번 : 순열 / 1777번 : 순열복원 (세그먼트 트리) (0) | 2021.12.14 |
[C++ 백준 풀이] 1306번 : 달려라 홍준 / 1572번, 9426번 : 중앙값 (측정) (슬라이딩 윈도우 알고리즘) (0) | 2021.12.13 |
[C++ 백준 풀이] 3653번 : 영화 수집 / 6213번, 6218번 : Balanced Lineup (0) | 2021.12.13 |