[백준] 9252번 : LCS2

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 1 ~ n 인덱스까지의 A 문자열이 있을 때, 1 ~ n 인덱스까지의 B 문자열과의 최장 공통 수열을 2차원 dp 배열에 차례대로 갱신하는 Bottom-Up 방식으로 풀었다.

• 이 문제는 기존 LCS 문제와 같으나, 개수 뿐만 아니라 해당 수열을 직접 출력까지 해야한다.
  따라서 LCS의 길이를 구하는 부분은 생략하고, 수열을 출력하는 부분만 알아보겠다.
  (9251번 : LCS 링크)

1) A 문자열의 길이가 n이고, B 문자열의 길이가 m이라고 할 때, dp[n][m]에는 A 문자열과 B 문자열 사이의 최장 증가 수열의 길이가 저장된다. 따라서 이 dp[n][m]까지 오는 경로를 역추적하면 최장 증가 수열이 어떤 문자로 구성되어있는지 알 수 있다.

2) 변수 i, j를 선언하고, 각각 n과 m으로 초기화한다. 또한 최장 증가 수열을 저장할 문자열 변수 answer를 선언한다.

3) i와 j가 모두 0이 될 때까지 아래 과정을 반복한다.

• 만약 str1[i] == str2[j]일 때(현재 순서 A 문자열의 글자와 B 문자열의 글자가 같을 때)
  • i와 j를 1씩 감소시키고, answer에 str1[i](현재 순서 글자)를 추가한다.
  • 두 문자열의 현재 순서 글자가 같은 글자일 때만 수열 길이가 증가하기 때문이다.
• 위 경우가 아니라면
  • 만약 dp[i][j] == dp[i - 1][j] 라면
    (A 문자열의 길이가 B 문자열보다 1 짧은 경우의 최장 증가 수열의 길이를 가져온 경우)
    • i를 1 감소시킨다.
  • 만약 dp[i][j] == dp[i][j - 1] 라면
    (B 문자열의 길이가 A 문자열보다 1 짧은 경우의 최장 증가 수열의 길이를 가져온 경우)
    • j를 1 감소시킨다.

4) answer에 최장 증가 수열이 뒤집힌 상태로 저장되어있으므로, 이를 반대로 출력한다.

🖥️ 풀이 코드

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

int n, m;
int dp[1001][1001];
string str1, str2, answer;

void solution()
{
	int maxCount = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (str1[i - 1] == str2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
				if (maxCount < dp[i][j])
				{
					maxCount = dp[i][j];
				}
			}
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	cout << dp[n][m] << endl;
	
	int i = n, j = m;
	while (i != 0 && j != 0)
	{
		if (str1[i - 1] == str2[j - 1])
		{
			answer += str1[i - 1];
			i--;
			j--;
		}
		else
		{
			if (dp[i][j] == dp[i - 1][j])
				i--;
			else if (dp[i][j] == dp[i][j - 1])
				j--;
		}
	}

	for(int i = answer.length() - 1; i >= 0; i--)
		cout << answer[i];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> str1;
	cin >> str2;
	n = str1.size();
	m = str2.size();
	solution();
}