풀이
잘 정리된 풀이가 있어서 풀이와 출처를 첨부합니다!
- 목적 함수 : Sum { Length(color) }
- Length(c) = LastIdx(c) - FirstIdx(c) + 1 이므로 결국, Sum { LastIdx } + Sum { -FirstIdx }를 최소화 시키는 문제로 볼 수 있다.
- 2개의 차 행렬은 앞에서부터 순차적으로 합쳐지기 때문에 첫 번째 차 행렬에서 i개의 차량이 합쳐지고, 두 번째 차 행렬에서 j개의 차량이 합쳐졌을 때를 상태 공간으로 삼아 동적계획법을 수행할 수 있다.
- 이를 D[i][j]라고 하자. 임의의 [i x j]에 대해 그 다음 차량을 합칠때 그 차량 색깔이 처음으로 등장하는지/마지막으로 등장하는 지 여부를 알 수 있으므로 2번의 목적 함수를 계산할 수 있다.
- 시간 복잡도는 O(N^2).
- N^2크기의 DP테이블을 잡으면 메모리 제한에 걸리지만 D[i][j]는 항상 D[i-1][j] 또는 D[i][j-1]에서 영향을 받으므로 2*N크기만의 DP테이블을 이용하는 방법으로 이를 피할 수 있다.
풀이 출처: https://algospot.com/wiki/read/ACM-ICPC_한국대회/2011
코드
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int len1, len2;
int dp[5002][5002], acc1[5002][26], acc2[5002][26];
char s1[5002], s2[5002];
inline int min(int a, int b) { return a < b ? a : b; }
void init() {
s1[0] = s2[0] = '*';
len1 = strlen(s1), len2 = strlen(s2);
memset(dp, 0x3f, sizeof(dp));
memset(acc1, 0, sizeof(acc1));
memset(acc2, 0, sizeof(acc2));
}
int get_len(int x, int y, int c) {
int ret1 = 0, ret2 = 0;
if (acc1[x][c] + acc2[y][c] == acc1[len1 - 1][c] + acc2[len2 - 1][c]) ret1 = x + y;
if (acc1[x][c] + acc2[y][c] == 1) ret2 = x + y;
return ret1 - ret2;
}
void solve() {
for (int i = 1; i < len1; i++) {
for (int j = 0; j < 26; j++) acc1[i][j] = acc1[i - 1][j];
acc1[i][s1[i] - 'A']++;
}
for (int i = 1; i < len2; i++) {
for (int j = 0; j < 26; j++) acc2[i][j] = acc2[i - 1][j];
acc2[i][s2[i] - 'A']++;
}
dp[0][0] = 0;
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
int ret1 = get_len(i + 1, j, s1[i + 1] - 'A');
int ret2 = get_len(i, j + 1, s2[j + 1] - 'A');
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + ret1);
dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + ret2);
}
}
}
int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
scanf("%s %s", s1 + 1, s2 + 1);
init();
solve();
printf("%d\n", dp[len1 - 1][len2 - 1]);
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이