백준 - 9252 LCS 2

문제

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

9252번: LCS 2

두 수열의 공통 부분 수열 중 가장 긴 것을 찾는 문제였다.

 

문제 풀이

dp를 사용해 풀었다. dp 점화식을 말에서 식으로 바꾸는 것이 조금 헷갈렸지만 표를 그려보니 바로 이해가 됐다.

주어진 예시를 이용해 dp 배열을 만들면 위와 같은 모양이 된다. 0행 1열은 AC와 C의 LCS 길이, 1행 2열은 ACA와 CA의 LCS 길이가 된다. 그 전 dp값의 max 값이 현재 dp 값이 되고, 만약 A와 B 문자열의 현재 위치의 문자가 같다면 +1 해줬다.

 

LCS 문자열은 마지막 문자에서 거슬러 올라가면서 구했다. 위와 왼쪽이 같은 길이가 아니라면 현재 위치에서 +1 된 것이기 때문에 정답 문자열에 추가했고 이와 같은 과정을 반복해 구했다.

 

string A, B;
int lengthA, lengthB;
vector<vector<int>> dp;

void printDP() {
	printf("  ");
	for (int i = 0; i < lengthB; i++) {
		printf("%c ", B[i]);
	}
	printf("\n");
	for (int i = 0; i < lengthA; i++) {
		printf("%c ", A[i]);
		for (int j = 0; j < lengthB; j++) {
			printf("%d ", dp[i][j]);
		}
		printf("\n");
	}
}

int leftLength(int x, int y) {
	y--;
	if (x < 0 || x >= lengthA || y < 0 || y >= lengthB) return -1;
	return dp[x][y];
}

int upLength(int x, int y) {
	x--;
	if (x < 0 || x >= lengthA || y < 0 || y >= lengthB) return -1;
	return dp[x][y];
}

int main() {

	//dp에서 A가 행, B가 열


	cin >> A;
	cin >> B;

	lengthA = A.length();
	lengthB = B.length();

	dp = vector<vector<int>>(lengthA, vector<int>(lengthB, 0));

	//테두리 dp 초기화
	if (A[0] == B[0]) dp[0][0] = 1;
	for (int i = 1; i < lengthA; i++) {
		if (A[i] == B[0]) dp[i][0] = 1;
		dp[i][0] = max(dp[i][0], dp[i - 1][0]);
	}
	for (int i = 1; i < lengthB; i++) {
		if (A[0] == B[i]) dp[0][i] = 1;
		dp[0][i] = max(dp[0][i], dp[0][i - 1]);
	}
	
	
	//나머지 dp 계산
	for (int i = 1; i < lengthA; i++) {
		for (int j = 1; j < lengthB; j++) {
			//max 값 만들기		
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

			if (A[i] == B[j]) { //맨 끝 글자와 같다면 +1
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
		}
	}

	//printDP();

	//LCS 문자열 찾기
	//위, 왼쪽으로 가면서 현재 length 마지막 위치 찾기
	string str = "";
	int nowLength = dp[lengthA - 1][lengthB - 1];
	int x = lengthA - 1;
	int y = lengthB - 1;
	while (true) {
		//printf("dp[%d][%d]: %d\n", x, y, dp[x][y]);		
		if (upLength(x, y) == nowLength) {
			x -= 1; 
			if (leftLength(x, y) == nowLength) {
				y -= 1;
			}
		}
		else if (leftLength(x, y) == nowLength) {
			y -= 1;
			if (upLength(x, y) == nowLength) {
				x -= 1;
			}
		}
		else { //왼쪽, 위 모두 다름 -> 여기에서 바뀜
			//printf("------------change!!----------\n");
			if (x == 0 && y == 0 && dp[0][0] == 0) break;
			str = A[x] + str;
			nowLength--;
			if (x == 0 && y == 0) break;
		}	
	}

	printf("%d\n", dp[lengthA-1][lengthB-1]);
	if(dp[lengthA - 1][lengthB - 1] != 0) 
		cout << str << endl;

	return 0;
}

/*

*/