28024 - White Light

작성일 | In

28024 - White Light
길이 $N(1\leq N\leq2\times10^5)$의 R, G, B로 이루어진 문자열 $S$가 있습니다. 길이 $K(1\leq N\leq2\times 10^5)$ 이하의 부분 문자열을 삭제하는 작업을 최소한으로 수행하여 문자열을 RGB...RGB꼴로 만드는 것이 목표입니다.

$dp[i][c]$을 $i$번째 문자열까지 보았을 때, 마지막을 문자 $c$​​로 끝내는데 필요한 최소 비용이라고 정의합니다.
그리고 $c’$를 $c$ 직전에 사용되었던 문자라고 정의합니다. ($c$가 B라면 $c’$는 G)

그렇다면 다음과 같이 dp table을 채울 수 있습니다.

$$ \begin{equation} dp[i][c] = \min \begin{cases} dp[i-1][c'] & \text{if}\ s[i] = c \\ \min\limits_{i-k-1\leq x< i-1} dp[x][c'] + 1 & \text {if}\ s[i] = c\\ \min\limits_{i-k\leq x\leq i-1} dp[x][c] + 1 \end{cases} \end{equation} $$

Base case로 $dp[0][2] = 0$, 나머지는 $\text{INF}$으로 미리 채워 둘 수 있습니다. (첫 R을 이전 B의 끝에서부터 시작한다고 생각하면 됩니다.)

위 dp table을 나이브하게 채우면 $O(N^2)$의 시간이 들지만, segment tree나 BIT같은 range minimum query point update를 지원하는 자료구조를 사용하면 $O(N\log N)$의 시간복잡도로 해결할 수 있습니다.

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
class SegmentTree {
public:
    vector<ll> seg;
    int n;
    SegmentTree(int n) {
        seg.resize(4 * n + 5, LLINF);
        this->n = n;
    }
    ll upd_(int idx, int l, int r, int pos, ll val) {
        if (pos < l || pos > r) return seg[idx];
        if (pos == l && pos == r) return seg[idx] = val;
        int mid = (l + r) / 2;
        return seg[idx] = min(
            upd_(idx * 2, l, mid, pos, val),
            upd_(idx * 2 + 1, mid + 1, r, pos, val)
            );
    }
    ll calc_(int idx, int l, int r, int tl, int tr) {
        if (tl > tr) return LLINF;
        if (tl == l && tr == r) return seg[idx];
        int mid = (l + r) / 2;
        return min(
            calc_(idx * 2, l, mid, tl, min(tr, mid)),
            calc_(idx * 2 + 1, mid + 1, r, max(mid + 1, tl), tr)
            );
    }
    void upd(int pos, ll val) {
        upd_(1, 0, n - 1, pos, val);
    }
    ll calc(int l, int r) {
        if(l < 0) l = 0;
        if(r < 0) r = 0;
        return calc_(1, 0, n - 1, l, r);
    }
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k; cin >> n >> k;
    string s; cin >> s;
    SegmentTree r(n+1), g(n+1), b(n+1);
    b.upd(0, 0);
    for(int i=1; i<=n; i++) {
        r.upd(i, r.calc(i-k,i-1) + 1);
        g.upd(i, g.calc(i-k,i-1) + 1);
        b.upd(i, b.calc(i-k,i-1) + 1);
        if(s[i-1] == 'R') {
            ll v = r.calc(i, i);
            ll v2 = b.calc(i-1, i-1);
            ll v3 = b.calc(i-k-1, i-2) + 1;
            r.upd(i, min({v, v2, v3}));
        } else if(s[i-1] == 'G') {
            ll v = g.calc(i, i);
            ll v2 = r.calc(i-1, i-1);
            ll v3 = r.calc(i-k-1, i-2) + 1;
            g.upd(i, min({v, v2, v3}));
        } else if(s[i-1] == 'B') {
            ll v = b.calc(i, i);
            ll v2 = g.calc(i-1, i-1);
            ll v3 = g.calc(i-k-1, i-2) + 1;
            b.upd(i, min({v, v2, v3}));
        }
    }
    cout << b.calc(n, n) << '\n';
}