백준 25097, Controlled Inflation

개요

문제 링크
골드 2, DP, Greedy
N명의 P개 작업을 최소한의 조작으로 마무리하기

---

접근

1. Codejam 2022 문제, codejam 문제는 시간을 많이줘서 생각이 맞으면 크게 틀리는 일이 없다. 문제는 생각이 어려움.

2. 해법은 완탐을 하면 되는데, 완탐 조건이 약간 까다롭다. 먼저 완탐의 방식부터 생각하면 한 구간의 시작과 끝을 기준으로 잡고 모든 (s,e)에 대해 최솟값을 구하면 된다. 즉,

    for (s1:start) {
        for (e1:end) {
            for (s2:start) {
                for (e2:end) {
                    value[s1][e1] = Minimum(previous[s2][e2])
                }
            }
        }
    }

   이런 느낌으로 가면 되고 Minimum은 앞에있는 모든 경우를 돌아보면서 최적값을 구해주는 것이다.

   1. 값을 구할 때 고려할 것은 두 가지 인데, 앞의 덩이의 끝과 현재 덩이의 시작과의 차이, 그리고 현재 덩이 내부에서 해야 할 조작이다. 차이는 abs를 써주면 되고, 구간 내부의 조작을 구할 때는 조금 복잡하다.

      조건	값
      양 끝이 최소 (단조증가)	최대-왼쪽 + 최대-오른쪽
      양 끝이 최대 (단조감소)	왼쪽-최소 + 오른쪽-최소
      둘 다 아니고 왼쪽이 큼 (N모양)	최대-왼쪽 + 최대-최소 + 오른쪽-최소
      둘 다 아니고 오른쪽이 큼 (뒤집은N)	왼쪽-최소 + 최대-최소 + 최대-오른쪽

      이렇게 하는 것이 최선이다. 때문에 구간마다 최대와 최소를 미리 구해둬야 한다. 주의할 점은 단조 증가 또는 감소가 아닌 경우에 왼쪽과 오른쪽을 비교해야 더 최적의 상황을 만들 수 있다는 것이다. 왼쪽이 더 높이 있는데 최솟값을 먼저 찍고 오면 손해니까.

   2. 여기까지 생각하고 5중 포문을 돌리면 되는데, 여기까지는 완탐이 잘 연습되어 있다면 크게 어렵지 않다.
      하지만 당연히 이렇게 하면 $O(NP^4)$이 되니까 시간에서 터진다. 변수를 몇개 추가해서 $O(NP^2)$까지 시간을 줄여줘야 한다.

3. 포문의 개수를 줄이기 위해 두 가지 그리디를 쓰는데, 먼저 첫번째 생각. 각 end마다 미리 최솟값을 구해놓는다. 왜냐하면 현재의 선택이 영향을 받는 것은 앞의 선택의 끝부분과 앞의 선택의 결과값이지 앞의 선택의 시작부분이 아니기 때문이다.

   1. 말이 어려운데 앞에서 10-20-30을 통해 오나 50-40-30을 통해 오나 끝이 30이고 구간 안에서 20의 비용이 들은 것은 차이가 없다는 말이다.
   2. 그럼 길이 p의 vector를 생성하고 매번 업데이트를 해준다.

4. 그리고 두 번째 생각. 어떤 시작값에 대해 항상 최적이 되는 앞덩이의 끝값이 존재한다. 굳이 앞덩이의 모든 s,e에 대해 완탐을 돌릴 필요가 없다. 첫번째 생각을 통해 s를 하나 줄여줘도 e에 대해서는 포문이 남아있게 되는데, 이걸 줄일 수 있는 방법이 된다. 값을 구할 때는 abs(x[i-1][e]-x[i][s]) + Min[e]를 통해 해주면 된다. Min[e]는 앞서 구해 둔 e에 대한 최솟값이다.

5. 그래서 최종적으로 s에 대한 큰 루프 안에서, 앞e에 대해루프를 돌면서 앞e의 최적값을 구해놓고, 현재 e에 대해 루프를 돌면서 각 e마다의 값을 저장하고 최솟값을 저장해둔다.

문제 자체가 엄청 복잡해보이는데 풀다보면 자연스레 느끼는 부분이 많았다. 예시도 잘 대입하다보면 크게 어렵지 않게 해결할 수 있다.

---

Pseudo code

Range(i, s, e) {
    s = x[i][s], e = x[i][e]
    if (s or e == min)
        return (2*max-s-e);
    if (s or e == max)
        return (s+e-2*min);
    if (s>e)
        return max-s + max-min + e-min;
    if (e<s)
        return s-min + max-min + max-e;
}

for (i = 1~n)
    for (start = 0~p)
        for (prevEnd = 0~p)
            prevMin = abs(x[i-1][prevEnd]-x[i][start]) + minEnd[prevEnd]
        for (curEnd = 0~p)
            dp[start][curEnd] = prevMin + Range(i, start, curEnd)
            minEnd[curEnd] = min(minEnd[curEnd], dp[s][e])

---

Source code

#include <bits/stdc++.h>
using namespace std;

using ld = long long;
using vec = vector<ld>;
using mat = vector<vec>;
const ld N = 1010, P = 110;
#define all(a)    a.begin(), a.end()
#define mine(a) *min_element(all(a))
mat x(N, vec(P));
vec l(N), r(N); // 구간 최대, 최소

ld value(int i, int s, int e) {
    if (x[i][s] == l[i] || x[i][e] == l[i]) {
        return 2 * r[i] - x[i][s] - x[i][e];
    } else if (x[i][s] == r[i] || x[i][e] == r[i]) {
        return x[i][s] + x[i][e] - 2 * l[i];
    } else {
        return 2 * r[i] - 2 * l[i] - abs(x[i][s] - x[i][e]);
    }
};

void test() {
    int n, p;
    cin >> n >> p;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < p; j++) {
            ld &a = x[i][j];
            cin >> a;
            if (j == 0) l[i] = r[i] = a;
            r[i] = max(r[i], a);
            l[i] = min(l[i], a);
        }
    }

    mat dp(p, vec(p));
    vec minv(p, 0), t(p); // 끝마다 최소배열, 복사에 사용할 배열
    for (int i = 1; i <= n; i++) {
        for (int s = 0; s < p; s++) {
            ld m;
            // 앞 e에 대해 루프
            for (int e = 0; e < p; e++) {
                auto v = abs(x[i][s] - x[i - 1][e]) + minv[e];
                if (e == 0) m = v;
                m = min(m, v);
            }
            // 현재 e에 대해 루프
            for (int e = 0; e < p; e++) {
                auto &a = dp[s][e];
                a = m + value(i, s, e);
                if (s == 0) t[e] = a;
                t[e] = min(t[e], a);
            }
        }
        minv = t;
    }
    cout << mine(minv) << "\n";
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        test();
    }
}