[백준] 7620 편집 거리

문제 링크

http://icpc.me/7620

7620번: 편집 거리

풀이

dp 역추적을 하는 문제다. 하지만 메모리를 특이하게 관리해야 하는 처음 보는 문제다.

역추적을 하기 위해서 dp테이블을 모두 가지고 있기엔 테이블의 크기가 17000 * 17000 * 4byte로 너무 크다.

그렇기 때문에 역추적을 위한 테이블을 17000 * 17000 * 2bit로 만들어 메모리를 최적화시켜야 한다.

역추적 테이블은 unsigned char 한 칸에 비트 연산을 이용하여 정보를 4개씩 담으면 된다. 

처음엔 char로 했는데 최상위 비트가 1이면 음수 처리돼 문자가 발생해 unsigned char로 바꿨다.

1. a[i] == b[i]인 경우 : dp[i][j] = dp[i - 1][j - 1]

2. a[i] != b[i]인 경우 : dp[i][j] = min(dp[i - 1][j], dp[i][j -1], dp[i - 1][j - 1]) + 1

dp 점화식은 위와 같다. 이 dp를 i번째 구할때 i..i-2까지 사용하지 않는 것을 이용하여 2줄짜리 dp로 바꾸면 된다.

히르쉬버그? 뭔진 모르겠는데 그거 쓰면 메모리를 O(n)만 쓰고도 가능하다는데 그렇게 변형된 문제는 다이아다. 나아아ㅏ아중에 공부할게 생겼다.

코드

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

const int N = 18000;
int dp[2][N];
unsigned char par[N / 2][N / 2];
string a, b;

int q(int r, int c) {
    int r_mod = r % 2, c_mod = c % 2;
    r = r / 2, c = c / 2;
    int k = par[r][c];
    if (!r_mod && !c_mod) return k & 3;
    else if (!r_mod && c_mod) return (k >> 2) & 3;
    else if (r_mod && c_mod) return (k >> 4) & 3;
    else return (k >> 6) & 3;
}

// m 0, 왼쪽 1, 위 2, c 3

void u(int r, int c, int t) {
    int r_mod = r % 2, c_mod = c % 2;
    r = r / 2, c = c / 2;
    auto &k = par[r][c];

    if (!r_mod && !c_mod) k |= t;
    else if (!r_mod && c_mod) k |= (t << 2);
    else if (r_mod && c_mod) k |= (t << 4);
    else k |= (t << 6);
}

void print(int r, int c) {
    if (!r && !c) return;
    int prv = q(r, c);
    if (prv == 0) {
        print(r - 1, c - 1);
        printf("m %c\n", b[c]);
    } else if (prv == 1) {
        print(r, c - 1);
        printf("a %c\n", b[c]);
    } else if (prv == 2) {
        print(r - 1, c);
        printf("d %c\n", a[r]);
    } else {
        print(r - 1, c - 1);
        printf("c %c\n", a[r]);
    }
}

int main() {
    cin >> a >> b;
    a = '%' + a; b = '%' + b;
    for (int i = 0; i < max(a.size(), b.size()); i++) {
        u(0, i, 1);
        u(i, 0, 2);
        dp[0][i] = i;
    }
    
    for (int i = 1; i < a.size(); i++) {
        dp[1][0] = i;
        for (int j = 1; j < b.size(); j++) {
            if (a[i] == b[j]) {
                dp[1][j] = dp[0][j - 1];
                u(i, j, 3);
            } else {
                dp[1][j] = min({dp[0][j - 1], dp[0][j], dp[1][j - 1]}) + 1;
                if (dp[1][j] == dp[0][j - 1] + 1) u(i, j, 0);
                else if (dp[1][j] == dp[1][j - 1] + 1) u(i, j, 1);
                else u(i, j, 2);
            }
        }
        for (int i = 0; i < b.size(); i++) {
            dp[0][i] = dp[1][i];
            dp[1][i] = 0;
        }
    }
    print(a.size() - 1, b.size() - 1);
}