사실 이게 뭔진 모르겠지만 나 스스로 뭔가 흥미로운 방법으로 문제를 풀고 있는 것 같아 기록해둔다.
일단 이 문제를 보자.
https://www.acmicpc.net/problem/19598
19598번: 최소 회의실 개수
서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의
www.acmicpc.net
회의를 모두 진행할 수 있는 회의실의 최소를 구하는 것이다.
나는 이렇게 풀었다.
1. 빨리 끝나는 순서로 정렬한다. 끝나는 순서가 같으면 시작하는 시간이 빠른 순서로 정렬한다.
2. multiset<int>을 준비한다. 첫 번째 회의는 trivial case로 두어 첫 번째 회의가 끝나는 시간을 넣는다.
3. 다음 회의부터 시작하는 시간에 대해 upper_bound를 한다.
4-1. 만약 반환된 iterator가 begin이 아니라면 해당 회의가 시작하는 시간보다 더 일찍 끝나는 회의가 있다는 뜻이다. 해당 itertator로 이동하여(하나 빼기) 원소를 제거하고(원래 있던 끝나는 시간을 빼고) 현재 회의가 끝나는 시간을 삽입한다.(해당 회의실에서 가장 늦게 끝나는 회의를 갱신)
4-2. 반환된 iterator가 begin이라면 적절히 이을 수 있는 회의가 없다는 뜻이다. 따라서 이 회의가 끝나는 시간을 새로 multiset에 삽입한다.
5. 모든 회의에 대해 3~4를 반복한 후 multiset의 크기가 정답이다.
코드는 다음과 같다.
|
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
|
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
#include "ext/rope"
using namespace std;
using namespace __gnu_cxx;
using ll = int_fast64_t;
using pii = pair<int, int>;
int n;
pii ar[100000];
void solve()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> ar[i].first >> ar[i].second;
}
sort(ar, ar + n, [](pii &l, pii &r) {
return l.second != r.second ? l.second < r.second : l.first < r.first;
});
multiset<int> st;
for (int i = 0; i < n; i++)
{
auto [l, r] = ar[i];
if (st.empty())
{
st.insert(r);
continue;
}
auto it = st.upper_bound(l);
if (it == st.begin())
{
st.insert(r);
continue;
}
--it;
st.erase(it);
st.insert(r);
}
cout << st.size();
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin.tie(nullptr);
ios::sync_with_stdio(false);
solve();
}
|
cs |
처음 풀 때는 이 풀이를 대수롭지 않게 생각했으나 최근 이 방법이 LIS와 연관이 있다는 것을 짐작하게 되었다.
다음 문제를 보자.
https://www.acmicpc.net/problem/10651
10651번: Cow Jog
Farmer John's N cows (1 <= N <= 100,000) are out exercising their hooves again, jogging along an infinite track. Each cow starts at a distinct position on the track, and some cows run at different speeds. The track is divided into lanes so that cows may
www.acmicpc.net
난이도가 갑자기 플래티넘으로 격상하지만 몇몇 관찰을 거치고 나면 위와 비슷한 방법으로 문제를 풀 수 있다.
다음 관찰을 한다.
문제에 나오는 소를 원소 $a_{i}$라고 표현해보자. 그러면 다음 사실이 따라온다.
임의의 두 소 $a_{i}, a_{j}$에 대해 $a_{i}$의 T초 후 위치가 $a_{j}$의 T초 후 위치보다 작다면 이 둘은 충돌하지 않는다.
그러면 우리는 소의 T초 후 위치에 주목하여 문제를 풀 수 있다. 어쨌든 충돌하지 않을 때까지 소들을 계속 이을 수 있기 때문이다.
풀이는 다음 과정을 따른다.
1. 마지막 소의 T초 후 위치는 trivial case로 multiset에 삽입한다. 이 문제는 앞에 소가 뒤의 소와 충돌하는지 검사하는 게 중요하기 때문에 마지막 소부터 첫 번째 소까지 반복을 돌 것이다.
2. 다음(i - 1) 소부터 해당 소의 T초 후 위치에 대해 upper_bound를 구한다.
3-1. iterator가 end가 아니면 찾아낸 소의 T초 후 위치보다 더 작은 위치에 존재, 즉 충돌하지 않음을 의미한다. 따라서 찾아낸 원소를 교체한다.
3-2. end면 적절히 낄 수 있는 곳이 없다는 뜻이므로 새로 삽입한다.
4. multiset의 크기가 정답
전체 코드
|
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
|
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
#include "ext/rope"
using namespace std;
using namespace __gnu_cxx;
using ll = int_fast64_t;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
int n;
ll t;
pll ar[100001];
multiset<ll> st;
void solve()
{
cin >> n >> t;
for (int i = 0; i < n; i++)
{
cin >> ar[i].first >> ar[i].second;
}
for (int i = n - 1; i >= 0; i--)
{
auto [go, speed] = ar[i];
ll dest = go + speed * t;
if (st.empty())
{
st.insert(dest);
continue;
}
auto it = st.upper_bound(dest);
if (it == st.end())
{
st.insert(dest);
}
else
{
st.erase(it);
st.insert(dest);
}
}
cout << st.size();
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin.tie(nullptr);
ios::sync_with_stdio(false);
solve();
}
|
cs |
이렇게 비슷하게 multiset을 활용하여 문제를 풀 수 있다. 세간에서는 이걸 LDS/LIS cover라고 부르는 거 같은데 구사과의 블로그에 따르면 이런 종류의 문제에 대해 나와 비슷하게 풀었다는 모양이다.
이런 개념을 몰라도 그리디하게 풀 수 있다. 아마 std::set 에 현재 Chain의 열 번호를 관리하고 행이 증가하는 순으로 처리하며 가장 가까운 열을 매칭시키는 풀이일 것이다. 나도 옛날에 그런 풀이를 짰는데, 알고보니 그냥 내가 $O(n \log n)$ 에 LIS를 구하고 있었다는 사실을 깨닫고 놀란 적이 있었다.
출처: https://koosaga.com/281
[구사과:티스토리]
아무튼 나도 놀랍다. 자 그러면 구사과 블로그에 언급된 ICPC 기출을 이 포스트에서 언급한 방법으로 풀어보자.
https://www.acmicpc.net/problem/23248
23248번: Treasure Hunter
Your program is to read from standard input. The input starts with a line containing three integers, $m$, $n$, and $k$ ($1 \le m, n, k \le 100,000$), where $m$ is the number of rows, $n$ is the number of columns of the map, and $k$ is the number of treasur
www.acmicpc.net
이 포스트를 착실하게 따라왔다면 쉽게 풀 수 있을 것이다.
사실 아직도 LIS 커버니 LDS 커버니 잘 와닿지는 않는다. 하지만 이런 방법으로 풀 수 있는 문제가 있다는 것을 더 보게되면서 기억해두면 확실히 좋을 거 같다.
'CP Algorithm & Knowledge' 카테고리의 다른 글
| pb_ds의 간단한 고찰 - 트리 구현체 (0) | 2022.09.15 |
|---|---|
| 2차원 평면에서 모든 점 쌍의 유클리드 거리 합 구하기 (0) | 2022.09.11 |
| Dynamic Segment Tree and Lazy Propagation (0) | 2022.09.06 |
| 세그먼트 트리로 직사각형 스위핑 feat. 3392 화성 지도 (0) | 2022.07.28 |
| KMP 알고리즘으로 부분 문자열 효과적으로 제거하기 (0) | 2022.07.23 |
