[백준] 9252-LCS 2(C++)

문제링크:www.acmicpc.net/problem/9252

9252번: LCS 2

 

LCS문제입니다.

 

LCS에 대한 설명은 아래 링크를 참고하세요

gusdnr69.tistory.com/192

LCS 알고리즘이란? (최장 공통 부분 수열)

 

해당 문제에서는 부분수열을 출력해야합니다.

 

이때 역순으로 올라가면서 하나씩 저장해준후에, 

역순으로 출력해주면 됩니다.

아래는 알파벳을 저장하는 코드입니다.

	int col = a.size() - 1;
	int row = b.size() - 1;

	while (dp[row][col]) {

		if (dp[row][col] == dp[row - 1][col]) {
			row--;
		}
		else if (dp[row][col] == dp[row][col - 1]) {
			col--;
		}
		else {
			result += a[col];
			row--, col--;
		}

	}

 

 

아래는 전체 정답코드입니다.

#include<iostream>
#include <string>
#include <algorithm>
using namespace std;
string a, b;
string result;
int dp[1001][1001] = { 0, };

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string temp1, temp2;
	cin >> temp1;
	cin >> temp2;
	
	a = ' ' + temp1;
	b = ' ' + temp2;
	
	
	for (int i = 1; i < b.size(); i++) {
		for (int j = 1; j < a.size(); j++) {
			if (a[j] == b[i]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	
	
	int col = a.size() - 1;
	int row = b.size() - 1;

	while (dp[row][col]) {

		if (dp[row][col] == dp[row - 1][col]) {
			row--;
		}
		else if (dp[row][col] == dp[row][col - 1]) {
			col--;
		}
		else {
			result += a[col];
			row--, col--;
		}

	}

	cout << dp[b.size() - 1][a.size() - 1] << endl;
	if (result.size() > 0) {
		reverse(result.begin(), result.end());
		cout << result << endl;
	}
	return 0;
}

 

a와 b 앞에 ' '를 추가해주면서 1base로 시작할 수 있도록 만들었습니다.