13940번: Pohlepko

https://www.acmicpc.net/problem/13940

$O(n^2+m^2)$

길이 l짜리 단어들 중 사전순으로 가장 빠른 단어는 다른 단어들과 앞의 i(i<l)개의 문자를 가지고 사전순 비교를 해도 가장 빠르다.
따라서 앞에서부터 보며 사전순으로 가장 빠르지 않은 문자를 가진 단어들을 해집합에서 제거해 나감으로써 최종 답을 구할 수 있다.

이러한 성질에 따라 / 모양의 대각선을 위에서 아래로 훑으면서 걸치는 문자들에 대해 사전순 비교를 한다.
이 중 가장빠른 문자에 대해 아래 혹은 오른쪽의 문자를 붙여 문자열을 만들 수 있으니 이를 고려하여 해집합을 구성한다.

#include<cstdio>
int n, m, ck[2000][2000];
char s[2000][2001], r;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", s[i]);
    ck[0][0] = 1;
    r = s[0][0];
    for (int i = 0; i < n + m - 1; i++) {
        putchar(r);
        char t = 'z';
        for (int j = 0; j <= i; j++) {
            int x = i - j, y = j;
            if (x >= n || y >= m || !ck[x][y] || s[x][y] ^ r) continue;
            if (x + 1 < n&&t >= s[x + 1][y]) ck[x + 1][y] = 1, t = s[x + 1][y];
            if (y + 1 < m&&t >= s[x][y + 1]) ck[x][y + 1] = 1, t = s[x][y + 1];
        }
        r = t;
    }
    return 0;
}