코드 복사/붙여넣기 하는 당신이 아름답습니다.

8902 : 색상의 길이

풀이

잘 정리된 풀이가 있어서 풀이와 출처를 첨부합니다!

  1. 목적 함수 : Sum { Length(color) }
  2. Length(c) = LastIdx(c) - FirstIdx(c) + 1 이므로 결국, Sum { LastIdx } + Sum { -FirstIdx }를 최소화 시키는 문제로 볼 수 있다.
  3. 2개의 차 행렬은 앞에서부터 순차적으로 합쳐지기 때문에 첫 번째 차 행렬에서 i개의 차량이 합쳐지고, 두 번째 차 행렬에서 j개의 차량이 합쳐졌을 때를 상태 공간으로 삼아 동적계획법을 수행할 수 있다.
  4. 이를 D[i][j]라고 하자. 임의의 [i x j]에 대해 그 다음 차량을 합칠때 그 차량 색깔이 처음으로 등장하는지/마지막으로 등장하는 지 여부를 알 수 있으므로 2번의 목적 함수를 계산할 수 있다.
  5. 시간 복잡도는 O(N^2).
  6. 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-12-03 17:20

Read more posts by this author