[Algorithm] cpp 백준 14177번: 티떱랜드

문제

링크: https://www.acmicpc.net/problem/14177
요약: 사람 1..N이 서 있는 순서를 바꾸지 않고 K개의 연속 구간으로 나눌 때, 각 구간(열차) 내 모든 사람쌍의 어색함 u_ij 합의 총합을 최소화합니다. 행렬 u는 대칭이고 대각선은 0입니다. 제약: \(1 \le N \le 4000\), \(1 \le K \le \min(N,800)\), \(0 \le u_{ij} \le 9\).

입력/출력

1
2
3
4
5
6
7
8
<입력>
N K
u11 u12 ... u1N
...
uN1 uN2 ... uNN   (대칭, uii=0)

<출력>
최소 가능한 전체 어색함 합

접근 개요

핵심 관찰: 구간 [l,r]의 어색함 비용은 \(\sum_{l \le i < j \le r} u_{ij}\). 대칭 행렬의 성질로 정사각형 부분합을 2로 나누면 빠르게 구할 수 있습니다.
전형적 구간 분할 DP: dp[g][i] = min_{0<=j<i}( dp[g-1][j] + cost(j+1, i) ).
cost(l,r)가 쌍대칭 합으로 정의되어 있어 분할정복 최적화(DnC Opt)가 성립합니다. 각 단계의 최적 j는 단조하게 이동하므로, O(N log N)에 한 레벨을 계산할 수 있습니다.

flowchart TB
  A[입력: N, K, 대칭 행렬 u] --> B[2D Prefix Sum P 구성]
  B --> C[cost(l,r) = sum(P, [l..r]x[l..r]) / 2]
  C --> D[DP 정의: dp[g][i] = min_j dp[g-1][j] + cost(j+1,i)]
  D --> E[Divide & Conquer Optimization로 dp[g][*] 계산]
  E --> F[정답 = dp[K][N]]

알고리즘 설계

비용 전처리(암시적): P[i][j]를 u의 2D 누적합으로 구성. 그러면 rect(l,l,r,r)를 \(O(1)\)에 얻고 cost(l,r) = rect/2.
DP 전이: g번째 그룹까지 고려해 앞에서 i명 채웠을 때의 최소 비용 dp[g][i].
DnC 최적화: i의 구간을 절반으로 쪼개며, 각 중간점의 최적 분할점 j*를 좌/우 재귀의 탐색 범위로 전달해 전체를 O(N log N)에 계산.
올바름 근거(요지):
- 동일 구간에 속하는 쌍의 비용만 더하므로, 구간 분할의 국소적 선택이 전체 비용에 선형 합으로 기여(가법성).
- 이때 최적 분할점이 단조하게 이동하는 구조(사각 부등식 계열)가 성립하여 DnC 최적화를 적용할 수 있습니다.

복잡도

시간: 전처리 O(N^2)(2D 누적합) + DP O(K N log N)
공간: O(N^2)(누적합) + O(N)(DP 레벨 2개)

구현 (C++)

 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
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    const int SZ = N + 1;
    // 2D prefix sum over the whole N x N matrix, flattened for cache locality
    vector<long long> psum(1LL * SZ * SZ, 0);
    auto I = [&](int r, int c) -> long long { return 1LL * r * SZ + c; };

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            int x; cin >> x;
            psum[I(i, j)] = psum[I(i - 1, j)] + psum[I(i, j - 1)] - psum[I(i - 1, j - 1)] + x;
        }
    }

    auto rect = [&](int r1, int c1, int r2, int c2) -> long long {
        return psum[I(r2, c2)] - psum[I(r1 - 1, c2)] - psum[I(r2, c1 - 1)] + psum[I(r1 - 1, c1 - 1)];
    };

    auto cost = [&](int l, int r) -> long long {
        // sum of u_ij for l <= i < j <= r; diagonal is zero; matrix symmetric
        long long s = rect(l, l, r, r);
        return s >> 1; // divide by 2
    };

    const long long INF = (1LL << 62);
    vector<long long> dp_prev(SZ, INF), dp_cur(SZ, INF);
    dp_prev[0] = 0;

    for (int g = 1; g <= K; ++g) {
        fill(dp_cur.begin(), dp_cur.end(), INF);

        function<void(int,int,int,int)> solve = [&](int L, int R, int optL, int optR) {
            if (L > R) return;
            int mid = (L + R) >> 1;

            long long bestVal = INF;
            int bestK = -1;

            int jStart = max(optL, g - 1);
            int jEnd = min(optR, mid - 1);
            for (int j = jStart; j <= jEnd; ++j) {
                long long cand = dp_prev[j] + cost(j + 1, mid);
                if (cand < bestVal) {
                    bestVal = cand;
                    bestK = j;
                }
            }
            dp_cur[mid] = bestVal;

            if (L == R) return;
            solve(L, mid - 1, optL, bestK);
            solve(mid + 1, R, bestK, optR);
        };

        solve(g, N, g - 1, N - 1);
        dp_prev.swap(dp_cur);
    }

    cout << dp_prev[N] << '\n';
    return 0;
}