BOJ 8902 색상의 길이

BOJ 8902 색상의 길이

[분류 : 그리디, 다이나믹 프로그래밍]

 

[풀이]
  하나의 색에 대해서만 생각해보자. 합쳐질 차선에 배치할 때 그 색상 중 가장 왼쪽에 올 수 있는 1차선의 후보와 2차선의 후보를 가려내보자. 순서상 같은 차선에서 같은 색상을 가지는 인덱스 i<j가 있다면 j는 절대로 가장 왼쪽에 올 수 없다. 따라서 각 차선에서도 가장 왼쪽의 차가 합친 차선의 같은 색상 중 가장 왼쪽에 올 후보가 될 수 있다. 이건 각 차선마다 최대 하나 존재하니, 색깔마다 두 개의 차선, 즉 후보는 최대 2개 존재한다.
  마찬가지로 가장 오른쪽의 후보도 위와 비슷한 논리로 최대 2개씩 존재한다.

  가장 왼쪽 후보군과 가장 오른쪽 후보군을 구한 이유는 같은 색상이지만 가장 왼쪽, 가장 오른쪽 두 쪽 모두 해당하지 않는 차들은 전부 고려할 필요가 없다. 문제에서 요구하는 것은 합친 차선에서 같은 색마다 가장 왼쪽과 가장 오른쪽의 거리를 모두 합한 값을 최소화하는 것이 목표기 때문에 처음과 끝이 정해져 있으면 중간에 뭐가 오든 거리값은 똑같다.

 

  따라서 배치할 때 이 후보군들을 가지고 처리하면 된다. 색과 시작을 뜻하는건지 끝을 뜻하는건지 상관없이 각 차선에서 후보가 될 수 있는 인덱스를 모두 끌어모은 다음 오름차순으로 접근하자.

 

F(i, a) = i-1차선의 a가 나타내는 인덱스  (예시)  1차선 : ABBBCDEEYAA  F[0] = {0, 1, 3, 4, 5  6, 7, 8, 10}  a=2, F[0][a] -> 3  a=5, F[0][a] -> 6 dp[a][b]=현재 1차선에서 a번째 후보와 2차선에서 b번째 후보를 사용할 수 있을 때 만족하는 최소 거리

  (거리를 계산해야하는 색의 수) 나는 후보를 하나씩 사용하면서 거리를 계산했다. 현재 후보군 위치가 (a, b)이므로 이 이전에 사용한 데이터를 가지고 현재 어떤 색상을 쓰고 있는지(이하 usedCnt) 또 그 색상을 모두 배치 했는지(이하 doneCnt)을 알 수 있다.
  각 색마다 가장 왼쪽과 가장 오른쪽을 저장했으므로, 가장 왼쪽을 나타내는 차가 1차선에선 F[0][a]보다 작거나(or), 2차선에선 F[1][b]보다 작다면 이 색상은 반드시 사용했음을 알 수 있다. 또 가장 오른쪽을 나타나는 차가 1차선에선 F[0][a]보다 작고(and), 2차선에서도 F[1][b]보다 작으면 그 색을 가진 차들은 모두 배치 끝났음을 알 수 있다.
  따라서 현재 (a, b) 상태에서 사용은 했지만 색 배치가 완전히 끝나지 않은 색의 수를 usedCnt - doneCnt로 구할 수 있다.

  (실제 거리 계산) 후보군만 사용해서 배치를 완료할 수 있음을 인지하자. 
  만약 상태 (a, b)에서 1차선의 F[0][a]를 사용했다고 치자. 이 후보군 a를 사용하기 위해선 F[0][a-1]부터 F[0][a]-1까지 모두 사용해야 한다. 그 사이의 거리는 F[0][a]-F[0][a-1]이다. 비슷하게 b를 선택할 때도 F[1][b] - F[1][b-1]로 구할 수 있다.
  단, 1차선에서 a까지 후보군이 아닌 모든 인덱스를 쓰고, 2차선에서 b까지 후보군이 아닌 모든 인덱스를 사용해야 최적이 나오는 경우가 있다. 가령 a, b모두 어떤 색의 시작을 나타내고 이전에 사용한 색 중 a, b가 나타내는 색보다 항상 늦게 배치 완료된다면 a,b 배치를 최대한 늦추는 것이 최적이기 때문이다.

  이를 위해 dp 형식을 살짝 변형한다.

 

dp[e1][e2][a][b] : 상태 (a, b). e1과 e2는 0 또는 1이며, 1이라면 그 차선에서 바로 직전까지 거리 계산을 이미 했음을 나타낸다.

 

  (주의) 색상이 두 차선에 존재하지 않을 수도 있고 한 차선에만 존재할 수도 있다. 설명하기 편하게하기 위해 굳이 위에서 얘기하지 않았으나 실제 풀이엔 이 경우도 고려해줘야 한다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 5e3, MAX_M = 53;
int p[2], st[2][26], ed[2][26], dp[2][2][MAX_M][MAX_M], F[2][MAX_M];
int rec(int e1, int e2, int a, int b) {
    if (a == p[0] && b == p[1]) return 0;
    int& ret = dp[e1][e2][a][b];
    if (ret != -1) return ret;
    ret = 1e9;
    int& p1 = F[0][a], & p2 = F[1][b], i, doneCnt = 0, usedCnt = 0;
    for (i = 0; i < 26; i++) {
        usedCnt += st[0][i] < p1 || st[1][i] < p2;
        if (ed[0][i] != -1 || ed[1][i] != -1)
            doneCnt += ed[0][i] < p1 && ed[1][i] < p2;
    }
    if (a < p[0]) {
        if (!e1)
            ret = rec(1, e2, a, b) + (a ? p1 - F[0][a - 1] - 1 : 1) * (usedCnt - doneCnt);
        ret = min(ret, rec(0, e2, a + 1, b) + (a && !e1 ? p1 - F[0][a - 1] : 1) * (usedCnt - doneCnt));
    }
    if (b < p[1]) {
        if(!e2)
            ret = min(ret, rec(e1, 1, a, b) + (b ? p2 - F[1][b - 1] - 1 : 1) * (usedCnt - doneCnt));
        ret = min(ret, rec(e1, 0, a, b + 1) + (b && !e2 ? p2 - F[1][b - 1] : 1) * (usedCnt - doneCnt));
    }
    return ret;
}
int main() {
    char A[MAX_N + 1];
    int T, i, j, k;
    scanf("%d\n", &T);
    while (T--) {
        memset(st, 0x3F, sizeof st);
        memset(ed, -1, sizeof ed);
        for (i = 0; i < 2; i++) {
            scanf("%s", A);
            for (j = 0; A[j]; j++) {
                k = A[j] - 'A';
                st[i][k] = min(st[i][k], j);
                ed[i][k] = max(ed[i][k], j);
            }
            p[i] = 0;
            for (j = 0; j < 26; j++) if (ed[i][j] != -1) {
                F[i][p[i]++] = st[i][j];
                F[i][p[i]++] = ed[i][j];
            }

            sort(F[i], F[i] + p[i]);
            p[i] = unique(F[i], F[i] + p[i]) - F[i];
            F[i][p[i]] = 55555;
        }

        memset(dp, -1, sizeof dp);
        printf("%d\n", rec(0, 0, 0, 0));
    }

    return 0;
}