문제
풀이
https://www.acmicpc.net/problem/8330
이 문제와 비슷한 방식으로 접근할 수 있습니다.
카드 주머니가 N개 있고, 주머니 안에는 각각 1 ~ Ai가 적힌 카드가 있습니다.
여기서 연속된 K개의 카드 주머니를 고르고, 그 카드 주머니에서 카드 하나씩 꺼내서
1, 2, 3, ...., K까지 하나씩 등장하도록 만들어야 하고, 이 때 K의 최댓값을 구하는 문제입니다.
이 문제는 고민만 하다가 끝났었는데 Two Pointer + Segment Tree Lazy로 풀리는 문제였습니다.
트리에는 해당 숫자를 몇 번 사용할 수 있는지 카운팅을 해줍니다.
만약 N = 5라면 1은 1번, 2는 2번, 3은 3번, 4는 4번, 5는 5번 사용할 수 있게 됩니다.
주머니의 크기가 5 5 5 5 5라면 크기가 5인 주머니를 5번 사용할 수 있으며, 5 5 5 5 5 5로는 6을 만들 수 없습니다.
그 다음에는 l = 0, r = 0으로 시작하여 해당 범위에 속한 K개를 모두 사용하여 1 ~ K까지 하나씩 만들 수 있는지 확인합니다.
r번째 주머니를 사용한게 되기 때문에 list[r] ~ maxValue의 범위에 -1씩 카운팅을 해줍니다.
이 과정에서 트리의 값이 음수가 되었다면 1 ~ K를 고르지 못한게 됩니다.
그래서 다시 음수에서 벗어날때까지 l을 오른쪽으로 이동시켜줍니다.
트리의 값이 음수인 것을 빠르게 캐치하려면 트리에 최솟값을 저장해야 합니다.
5
1 1 2 5 3예시로 설명드리면
맨 처음 트리의 상태는 1 2 3 4 5이고, 최솟값은 1입니다. (l = 0, r = 0)
여기서 범위를 오른쪽으로 1칸 늘립니다. (l = 0, r = 1)
값이 1이기 때문에 1 ~ 5의 카운팅을 1씩 감소시킵니다.
그러면 트리의 상태는 0 1 2 3 4가 되고, 최솟값은 0입니다.
다음 범위를 오른쪽으로 1칸 늘립니다. (l = 0, r = 2)
값이 1이기 때문에 1 ~ 5의 카운팅을 1씩 감소시킵니다.
그러면 트리의 상태는 -1 0 1 2 3이 되고, 최솟값은 -1입니다.
이때 음수가 되었기 때문에 l을 오른쪽으로 1칸씩 이동시킵니다. (l = 1, r = 2)
직전 l번째 수는 1이었기 때문에 1 ~ 5의 카운팅을 1씩 늘립니다.
그러면 트리의 상태는 0 1 2 3 4가 되고, 최솟값은 0이 되어 1 ~ K를 다시 만들 수 있게 됩니다.
다음 범위를 오른쪽으로 1칸 이동합니다. (l = 1, r = 3)
값이 2이기 때문에 2 ~ 5의 카운팅을 1씩 감소합니다.
트리의 상태를 0 0 1 2 3이 되고, 최솟값은 0이기 때문에 범위를 갱신할 수 있습니다.
이 과정을 끝까지 반복하여 l ~ r의 범위를 최대로 만들 수 있습니다.
코드
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 50001
using namespace std;
int list[MAX], tree[MAX << 2], lazy[MAX << 2];
int N, maxValue;
void lazyUpdate(int node, int l, int r) {
if (!lazy[node]) return;
tree[node] += lazy[node];
if (l != r) {
lazy[node << 1] += lazy[node];
lazy[(node << 1) + 1] += lazy[node];
}
lazy[node] = 0;
}
int update(int node, int l, int r, int s, int e, int diff) {
lazyUpdate(node, l, r);
if (l > e || s > r) return tree[node];
if (s <= l && r <= e) {
tree[node] += diff;
if (l != r) {
lazy[node << 1] += diff;
lazy[(node << 1) + 1] += diff;
}
return tree[node];
}
int m = (l + r) >> 1;
return tree[node] = min(update(node << 1, l, m, s, e, diff), update((node << 1) + 1, m + 1, r, s, e, diff));
}
int query(int node, int l, int r, int s, int e) {
lazyUpdate(node, l, r);
if (l > e || s > r) return 1e9;
if (s <= l && r <= e) return tree[node];
int m = (l + r) >> 1;
return min(query(node << 1, l, m, s, e), query((node << 1) + 1, m + 1, r, s, e));
}
void init() {
for (int i = 1; i <= N; i++) {
update(1, 1, maxValue, i, maxValue, 1);
}
}
void func() {
init();
int ret = 1;
int l = 0;
int r = 0;
while (r < N) {
update(1, 1, maxValue, list[r], maxValue, -1);
while (query(1, 1, maxValue, list[r], maxValue) < 0) {
update(1, 1, maxValue, list[l], maxValue, 1);
l++;
}
r++;
ret = max(ret, r - l);
}
cout << ret << '\n';
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i];
maxValue = max(maxValue, list[i]);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'대회 > elice' 카테고리의 다른 글
| 엘리스 코드 챌린지 Day 9 격자 위의 ELICE (0) | 2024.07.24 |
|---|---|
| 엘리스 코드 챌린지 Day 8 강림제 (0) | 2024.07.23 |
| 엘리스 코드 챌린지 Day 7 계기판 조작하기 (0) | 2024.07.23 |
| 엘리스 코드 챌린지 Day 6 빨간 선과 파란 선 (0) | 2024.07.23 |
| 엘리스 코드 챌린지 Day 5 수열 복원 (0) | 2024.07.22 |