[BOJ] 9252 : LCS 2 - travelbeeee

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

---

[알고리즘풀이]

기본적인 틀은 LCS 문제와 같다.

( LCS 기본 문제 : https://travelbeeee.tistory.com/150 )

 

입력되는 2개의 문자열을 n1, n2 라고 하자. 그리고 다음과 같이 dp배열을 선언해 string과 int를 동시에 담아보자.

pair<string, int> dp[i][j]

dp[i][j].first : n1 의 i번째 문자, n2의 j번째 문자까지 중에서 최장 공통 부분 수열의 문자열.

dp[i][j].second : n1 의 i번째 문자, n2의 j번째 문자까지 중에서 최장 공통 부분 수열의 길이.

 

1) n1의 i번 째 문자와 n2의 j번 째 문자가 같다면.

dp[i][j].first = dp[i - 1][j - 1].first + n1[i - 1];  // 기존의 가장 큰 문자열에다가 현재 문자를 합쳐준다.
dp[i][j].second = dp[i - 1][j - 1].second + 1; // 기존의 가장 길이에다가 1을 더해준다.

 

i번 째 문자와 j번 째 문자가 같으므로 그 전인 (i -1)번 째 문자와 (j - 1)번 째 문자까지의 최대 길이에 1을 더해주면 된다.

또, (i - 1)번 째 문자와 (j - 1)번 째 문자까지의 최대 부분 수열에 현재 문자를 더해주면 된다.

 

2) n1의 i번 째 문자와 n2의 j번 째 문자가 다르다면.

  2-1) dp[i - 1][j].second < dp[i][j - 1].second)
           dp[i][j] = dp[i][j - 1];
  2-2)
           dp[i][j] = dp[i - 1][j];

 

i번 째 문자와 j번 쨰 문자가 다르면 지금 탐색하는 i, j 지점에서 길이가 길어지지 않으므로,

그전까지 탐색해온 값 중 가장 큰 값과 그에 해당하는 문자열을 저장해준다.

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

pair<string, int> dp[1001][1001];

int main(void) {
	string n1, n2;
	cin >> n1 >> n2;
	int n = n1.length(), m = n2.length();

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (n1[i - 1] == n2[j - 1]) {
				dp[i][j].first = dp[i - 1][j - 1].first + n1[i - 1];
				dp[i][j].second = dp[i - 1][j - 1].second + 1;
			}
			else {
				if (dp[i - 1][j].second < dp[i][j - 1].second)
					dp[i][j] = dp[i][j - 1];
				else
					dp[i][j] = dp[i - 1][j];
			}
		}
	cout << dp[n][m].second << '\n';
	cout << dp[n][m].first << '\n';
}

---