[BOJ 8902] 색상의 길이

문제 출처 : https://www.acmicpc.net/problem/8902

 

풀이 :

2차원 DP문제입니다.

두개의 라인이 존재하는데 각라인에서 몇대가 합류했는지를 DP로 쌓으시면 됩니다.

저는 cache[line1][line2]의 형태로 저장했습니다.

 

문제에서 원하는 결과값은 결국 모든 끝나는 지점에서 모든 시작지점을 뺀 값과 같습니다

따라서 cache를 쌓을때 각 색깔별로 맨처음과 맨끝이 어디있는지를 비교하여

1. 그 색깔에서 맨 처음 나왔을 경우 : 그 위치를 (-) 해줌

2. 그 색깔에서 맨 마지막에 나왔을 경우 : 그 위치를 (+) 해줌

위의 두개지 규칙을 적용하여 풀었습니다.

#include<stdio.h>
#define MIN(A,B) ((A)<(B)?(A):(B))
int t, n, cache[5001][5001], f[2][26], l[2][26], i, j;
char line1[5001], line2[5001];
 
int main()
{
    scanf("%d\n", &t);
    while (t--) {
        scanf("%s", line1 + 1);
        scanf("%s", line2 + 1);
        for (i = 1; line1[i] != '\0'; i++)f[0][(int)(line1[i] - 'A')] == 0 ? f[0][(int)(line1[i] - 'A')] = l[0][(int)(line1[i] - 'A')] = i : l[0][(int)(line1[i] - 'A')] = i;
        for (j = 1; line2[j] != '\0'; j++)f[1][(int)(line2[j] - 'A')] == 0 ? f[1][(int)(line2[j] - 'A')] = l[1][(int)(line2[j] - 'A')] = j : l[1][(int)(line2[j] - 'A')] = j;
        for (int y = 0; y < i; y++)for (int x = 0; x < j; x++)cache[y][x] = 987654321;
        cache[0][0] = 0;
        line1[0] = line2[0] = '/';
        for (i = 0; line1[i] != '\0'; i++)for (j = 0; line2[j] != '\0'; j++) {
            int ret1=0, ret2=0;
            if (line1[i + 1] != '\0') {
                if (f[0][(int)(line1[i + 1] - 'A')] == i + 1 && (f[1][(int)(line1[i + 1] - 'A')] == 0 || f[1][(int)(line1[i + 1] - 'A')] > j))ret1 = -(i + j + 1);
                if (l[0][(int)(line1[i + 1] - 'A')] == i + 1 && l[1][(int)(line1[i + 1] - 'A')] <= j)ret1 += i + j + 1;
            }
            if (line2[j + 1] != '\0') {
                if (f[1][(int)(line2[j + 1] - 'A')] == j + 1 && (f[0][(int)(line2[j + 1] - 'A')] == 0 || f[0][(int)(line2[j + 1] - 'A')] > i))ret2 = -(i + j + 1);
                if (l[1][(int)(line2[j + 1] - 'A')] == j + 1 && l[0][(int)(line2[j + 1] - 'A')] <= i)ret2 += i + j + 1;
            }
            cache[i + 1][j] = MIN(cache[i][j] + ret1, cache[i + 1][j]);
            cache[i][j + 1] = MIN(cache[i][j] + ret2, cache[i][j + 1]);
        }
        printf("%d\n", cache[i - 1][j - 1]);
        for (int i = 0; i < 2; i++)for (int j = 0; j < 26; j++)f[i][j] = l[i][j] = 0;
    }
}