BOJ 34096 - 자동 광고 배치 시스템

문제

대회 때 팀원한테 살짝 문제 설명만 듣고, 잡진 않았는데 생각보다 할 만한 문제이다. 그냥 대회때 A를 잡지 말고 이 문제를 잡을 걸 그랬다.

 

문제 요약:

수 $N$개가 주어진다. 당신은 다음 행동을 반복해야 한다.

• 남은 수가 2개 이상이라면, 맨 앞의 수 3개 중 2개를 골라 삭제한다. 이 연산의 비용은 max(삭제하는 두 수)이다.
• 남은 수가 1개라면, 그 수를 삭제한다. 이 연산의 비용은 삭제하는 수와 같다.

모든 수를 삭제하는 데 드는 최소 비용을 구하라.

 

풀이:

그리디로 접근하는 순간 망한다.

 

다음과 같은 2차원 DP를 생각해 보자.

$DP[i][j] = $$i$번째까지 봤을 때, $j$만 남기고 다른 수를 모두 삭제하는 데 드는 경우의 수

이때, $i$번째까지 봤을 때 수가 하나만 남으려면, $i-3$이 짝수여야 한다. 따라서 $i-3$이 짝수일 때만 위 DP식이 정의된다고 하자. 

 

DP 전이 방식은 다음과 같다.

 

모든 $k$에 대해, 

$DP[i][k] = DP[i-2][k] + \max(A[i-1], A[i])$ (1)

$DP[i][A[i]] = \min (DP[i-2][k] + \max(k, A[i-1])$ (2)

$DP[i][A[i-1]] = \min(DP[i-2][k] + \max(k, A[i])$ (3)

 

 

위 식을 해석해보자.

현재까지 $A[1], ..., A[i-2]$를 잘 처리해서 $k$만 남기고 삭제하는 최소 비용이 곧 $DP[i-2][k]$이다.

그렇게 삭제하고 나면, 맨 앞의 수 3개에는 $k, A[i-1], A[i]$가 오게 된다.

 

(1)번 식은 $k$를 남기고 나머지 둘을 삭제하는 경우, (2)번 식은 $A[i]$를 남기는 경우, (3)번 식은 $A[i-1]$을 남기는 경우이다.

 

가능한 $k$의 후보는 $A[1], ..., A[N]$밖에 없으므로, 좌표 압축을 통해 $k$를 인덱싱해주면 $O(N^2 \log N)$ 풀이가 나온다.

 

이제 이 풀이를 $O(N \log N)$으로 최적화해보자.

편의상 모든 인덱스는 좌표 압축을 적용하기 전 기준으로 설명한다.

 

(1)번 식은 모든 $k$에 대해 같은 값을 더하는 것이다. 따라서 offset을 관리해주는 것으로 $O(1)$에 전이 가능하다.

 

(2)번 식을 어떻게 전이할지 생각해 보자.

 

먼저, $k \leq A[i-1]$인 경우와 $A[i-1] < k$인 경우로 나누자.

$k \leq A[i-1]$인 경우, $\max$ 식을 풀어서 $DP[i][A[i]] = \min(DP[i-2][k] + A[i-1])$으로 계산할 수 있다. 세그먼트 트리의 Range Minimum Query로 계산 가능한 형태이다.

 

$A[i-1] < k$인 경우, 역시 $\max$ 식을 풀어서 $DP[i][A[i]] = \min(DP[i-2][k] + k)$로 계산할 수 있다. 이는 세그먼트 트리에 약간의 변형을 가해 계산 가능하다. 세그먼트 트리에서 $k$번째 값이 $DP[i-2][k] + k$를 갖도록 하면 된다.

 

따라서, 두 개의 세그먼트 트리 seg1과 seg2를 관리한다. seg1의 $k$번째 값은 $DP[i][k]$이고, seg2의 $k$번째 값은 $DP[i][k] + k$이다. DP값을 업데이트할 때 사용하는 점 업데이트, 전이에 사용되는 구간 최솟값 쿼리와 offset을 사용한 전체 덧셈 쿼리를 지원하면 충분하다.

 

DP값을 전이할 때, seg1은 $[1, A[i-1]]$의 범위에 쿼리를 날리고, seg2는 $[A[i-1]+1, k]$에 쿼리를 날리면 된다. 물론 실제로 $[1, A[i-1]]$에 쿼리를 날리는 것이 아니라, 좌표 압축을 적절히 적용해서 대응되는 범위에 쿼리를 날리면 된다.

 

$N-3$이 짝수라면, 마지막에는 수가 하나 남게 된다. 모든 $k$에 대해 $DP[N][k]+k$의 최솟값이 답이다.

$N-3$이 홀수라면, 마지막에는 수가 두 개 남게 된다. 이 중 $A[N]$은 반드시 남는다. (수가 4개 남았을 때, $A[N]$은 삭제될 수 없는 위치에 있으므로 삭제되지 않는다.) 따라서 모든 $k$에 대해 $DP[N-1][k]+\max(k, A[N])$의 최솟값이 답이다.

 

총 $O(N\log N)$에 해결 가능하다.

 

코드:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Segtree
{
    vector<ll> seg;
    ll N, add;
    Segtree(ll n)
    {
        N = n;
        add = 0;
        seg.resize(4 * n + 100);
        fill(seg.begin(), seg.end(), 1e18);
    }
    ll query(ll l, ll r)
    {
        return query(1, 1, N, l, r) + add;
    }
    ll query(ll n, ll s, ll e, ll l, ll r)
    {
        if (r < s || e < l)
            return 1e18;
        if (l <= s && e <= r)
            return seg[n];
        ll m = (s + e) / 2;
        return min(query(2 * n, s, m, l, r), query(2 * n + 1, m + 1, e, l, r));
    }
    void add_all(ll x)
    {
        add += x;
    }
    void update(ll i, ll x)
    {
        update(1, 1, N, i, x - add);
    }
    void update(ll n, ll s, ll e, ll i, ll x)
    {
        if (i < s || e < i)
            return;
        if (s == e)
        {
            seg[n] = min(seg[n], x);
            return;
        }
        ll m = (s + e) / 2;
        update(2 * n, s, m, i, x), update(2 * n + 1, m + 1, e, i, x);
        seg[n] = min(seg[2 * n], seg[2 * n + 1]);
    }
};
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    ll T;
    cin >> T;

    while (T--)
    {
        ll N;
        cin >> N;
        vector<ll> v(N + 1);
        for (int i = 1; i <= N; i++)
            cin >> v[i];
        if (N == 1)
        {
            cout << v[1] << '\n';
            continue;
        }
        if (N == 2)
        {
            cout << max(v[1], v[2]) << '\n';
            continue;
        }
        vector<ll> c = vector<ll>(v.begin() + 1, v.end());
        sort(c.begin(), c.end());
        c.erase(unique(c.begin(), c.end()), c.end());
        Segtree seg1(N), seg2(N);

        for (int i = 1; i <= 3; i++)
        {
            ll ma = 0;
            for (int j = 1; j <= 3; j++)
            {
                if (i == j)
                    continue;
                ma = max(ma, v[j]);
            }
            ll t = lower_bound(c.begin(), c.end(), v[i]) - c.begin() + 1;
            seg1.update(t, ma);
            seg2.update(t, ma + v[i]);
        }
        // for (int i = 1; i <= N; i++)
        //     cout << seg1.query(i, i) << ' ';
        // cout << endl;
        for (int i = 4; i + 1 <= N; i += 2)
        {
            ll a = v[i], b = v[i + 1];
            ll ta = lower_bound(c.begin(), c.end(), a) - c.begin() + 1;
            ll tb = lower_bound(c.begin(), c.end(), b) - c.begin() + 1;

            ll sa = min(seg1.query(1, tb) + b, seg2.query(tb, N));
            ll sb = min(seg1.query(1, ta) + a, seg2.query(ta, N));

            seg1.add_all(max(a, b));
            seg2.add_all(max(a, b));

            seg1.update(ta, sa);
            seg2.update(ta, sa + a);

            seg1.update(tb, sb);
            seg2.update(tb, sb + b);

            // for (int i = 1; i <= N; i++)
            //     cout << seg1.query(i, i) << ' ';
            // cout << endl;
        }
        ll ans = 1e18;
        if ((N - 3) % 2 == 0)
            for (int i = 1; i <= c.size(); i++)
                ans = min(ans, seg1.query(i, i) + c[i - 1]);
        else
            for (int i = 1; i <= c.size(); i++)
                ans = min(ans, seg1.query(i, i) + max(c[i - 1], v[N]));
        cout << ans << '\n';
    }
}