[C/C++] 백준 9252번 - LCS 2 (Longest Common Subsequence, 최장 공통 부분 수열)

 

 

 

<코드>

#include<iostream>
#include<string>
#include<vector>
using namespace std;

string s1;
string s2;
string LCS[1001][1001];

int main()
{
	cin >> s1;
	cin >> s2;

	for (int i = 1; i <= s1.length(); i++)
	{
		for (int j = 1; j <= s2.length(); j++)
		{
			if (s1[i-1] == s2[j-1])
			{	// 왼쪽 대각 위의 LCS에서 이어 붙히기
				LCS[i][j] = LCS[i-1][j-1] + s1[i-1];
			}
			else
			{	// 왼쪽 LCS와 위쪽 LCS중 긴 LCS를 가져오기
				if(LCS[i-1][j].length() >= LCS[i][j-1].length())
					LCS[i][j] = LCS[i-1][j];
				else // (LCS[i-1][j] < LCS[i][j-1])
					LCS[i][j] = LCS[i][j-1];
			}
		}
	}

	cout << LCS[s1.length()][s2.length()].length() << '\n';
	cout << LCS[s1.length()][s2.length()] <<'\n';


}

 

풀이 방법

 

LCS(최장 공통 부분 수열) 알고리즘을 모른다면 풀기 까다로운 문제.

예전에 백준 9251번 : LCS 을 풀었었는데 그때의 풀이법을 까먹어서 제가 쓴 포스팅을 다시 찾아서 공부해서 풀이를 하였습니다. 역시 어려운 알고리즘의 경우는 반복적으로 봐야하는것 같습니다.

 

풀이방법은 아래의 포스팅을 참고하시면 될 것 같습니다.

cocoon1787.tistory.com/203

[C/C++] 백준 9251번 - LCS(Longest Common Subsequence, 최장 공통 부분 수열)

 

 

 

 

 

 

 

www.acmicpc.net/problem/9252

9252번: LCS 2