[Algorithm] cpp 백준 15977번: 조화로운 행렬

문제

링크: BOJ 15977: 조화로운 행렬
요약: 2×N 또는 3×N 행렬에서 열 몇 개를 골라 붙여 만든 열-부분행렬의 등수행렬이 모든 행에서 일치하도록 할 때, 가능한 최대 열 개수를 구한다. 원소는 모두 서로 다른 양의 정수이며, 등수는 각 행에서 내림차순 기준(큰 값 1등)이다.

입력/출력

입력: 첫 줄에 행의 개수 M(2 또는 3), 열의 개수 N(3 ≤ N ≤ 200,000). 이어서 M개의 줄에 각 행의 N개 원소가 주어진다.
출력: 조건을 만족하는 조화로운 열-부분행렬의 최대 열 개수.

예시 (문제 제공):

1
2
3
4
5
6
7
8
입력
3 9
10 74 41 15 89 52 16 63 75
30 53 22 33 46 45 25 47 21
29 49 13 26 59 17 62 34 19

출력
4

접근 개요

핵심 관찰: 선택한 열들의 각 행별 상대적 순위(등수)가 모든 행에서 동일해야 한다. 즉, 한 행을 기준으로 열을 정렬한 뒤 다른 행들의 등수열을 보면, 조화로운 부분은 모든 기준에서 동시에 증가하는 공통 순서가 된다.
모델링: 각 열 j를 각 행의 등수 (r1[j], r2[j], r3[j])로 표현하면, 답은 (r1, r2)의 증가 부분수열 길이(M=2) 또는 (r1, r2, r3)의 공증가 사슬 길이(M=3)와 같다. 여기서 r1은 정렬 기준이므로 자동 증가로 만들 수 있다.

알고리즘 설계

행별 등수 전처리

각 행을 값 오름차순으로 정렬하여 열 인덱스별 등수(1..N)를 부여한다. 이때 값이 모두 다르므로 동률 등수가 없다.

M=2: 1차원 LIS

1행 등수 순서대로 열을 나열하면 2행 등수의 수열이 된다. 이 수열의 길이가 조화로운 열-부분행렬의 최대 길이와 동일하다.
표준 LIS(O(N log N))로 계산한다. (Strictly increasing 필요)

M=3: 3차원 LIS → CDQ 분할정복 + Fenwick 트리

(k = r1, x = r2, y = r3) 튜플을 k 오름차순으로 정렬한다.
목표: k1 < k2, x1 < x2, y1 < y2를 만족하는 최대 길이 체인.
CDQ 분할정복으로 구간을 반으로 나누고, 왼쪽의 결과를 오른쪽으로 전파한다.
- 왼쪽/오른쪽을 x(=r2) 기준으로 정렬해 스위핑하며, y(=r3)에 대해 Fenwick에서 dp의 최댓값을 질의·갱신한다.
- x는 왼쪽 < 오른쪽, y는 y-1까지 질의하여 엄격 증가를 보장한다.
전체 시간복잡도는 O(N log^2 N), 공간복잡도는 O(N).

복잡도

M=2: 시간 O(N log N), 공간 O(N)
M=3: 시간 O(N log^2 N), 공간 O(N)

구현 (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
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick() : n(0) {}
    explicit Fenwick(int n_) { init(n_); }
    void init(int n_) {
        n = n_;
        bit.assign(n + 1, 0);
    }
    void update(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] = max(bit[idx], val);
    }
    int query(int idx) const {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res = max(res, bit[idx]);
        return res;
    }
    void clearIndex(int idx) {
        for (int i = idx; i <= n; i += i & -i) bit[i] = 0;
    }
};

struct Node {
    int k;   // rank in row1 (1..N)
    int x;   // rank in row2 (1..N)
    int y;   // rank in row3 (1..N), 0 if M=2
    int dp;  // LIS length ending here
};

int M, N;

void cdq_solve(vector<Node> &a, int l, int r, Fenwick &fw) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    cdq_solve(a, l, mid, fw);

    vector<int> L, R;
    L.reserve(mid - l + 1);
    R.reserve(r - mid);
    for (int i = l; i <= mid; ++i) L.push_back(i);
    for (int i = mid + 1; i <= r; ++i) R.push_back(i);

    auto by_x = [&](int i, int j) {
        return a[i].x < a[j].x;
    };
    sort(L.begin(), L.end(), by_x);
    sort(R.begin(), R.end(), by_x);

    vector<int> updatedYs;
    updatedYs.reserve(L.size());
    int p = 0;
    for (int idx : R) {
        while (p < (int)L.size() && a[L[p]].x < a[idx].x) {
            fw.update(a[L[p]].y, a[L[p]].dp);
            updatedYs.push_back(a[L[p]].y);
            ++p;
        }
        int best = fw.query(a[idx].y - 1); // strict y_left < y_right
        a[idx].dp = max(a[idx].dp, best + 1);
    }
    if (!updatedYs.empty()) {
        sort(updatedYs.begin(), updatedYs.end());
        updatedYs.erase(unique(updatedYs.begin(), updatedYs.end()), updatedYs.end());
        for (int y : updatedYs) fw.clearIndex(y);
    }

    cdq_solve(a, mid + 1, r, fw);
}

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

    if (!(cin >> M >> N)) return 0;
    vector<vector<int>> val(M, vector<int>(N));
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) cin >> val[i][j];
    }

    // ranks per row: 1..N (ascending by value)
    vector<vector<int>> rankRow(M, vector<int>(N));
    for (int i = 0; i < M; ++i) {
        vector<int> idx(N);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            return val[i][a] < val[i][b];
        });
        for (int pos = 0; pos < N; ++pos) rankRow[i][idx[pos]] = pos + 1;
    }

    // order columns by rank of row1
    vector<int> colByR1(N);
    for (int col = 0; col < N; ++col) colByR1[rankRow[0][col] - 1] = col;

    if (M == 2) {
        vector<int> seq;
        seq.reserve(N);
        for (int k = 0; k < N; ++k) {
            int col = colByR1[k];
            seq.push_back(rankRow[1][col]);
        }
        vector<int> tails;
        for (int x : seq) {
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end()) tails.push_back(x);
            else *it = x;
        }
        cout << (int)tails.size() << '\n';
        return 0;
    }

    vector<Node> nodes;
    nodes.reserve(N);
    for (int k = 0; k < N; ++k) {
        int col = colByR1[k];
        nodes.push_back(Node{ k + 1, rankRow[1][col], rankRow[2][col], 1 });
    }

    Fenwick fw(N);
    cdq_solve(nodes, 0, N - 1, fw);

    int ans = 0;
    for (const auto &nd : nodes) ans = max(ans, nd.dp);
    cout << ans << '\n';
    return 0;
}