[DP] 백준 9251 LCS C++

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

9251번: LCS

---

---

풀이 : 

LCS의 개념에 대해선 다음 글로 확인할 수 있습니다.

https://hoime.tistory.com/59?category=500438 

최장 공통 부분 수열(LCS)

 

주어진 첫 번째 문자열을 s1이라 하고 두번째 문자열을 s2라 할 때 차례대로 하나 씩 비교하고

dp[i][j] = s1의 i번째까지 문자열과 s2의 j번째 문자열 까지 공통되는 부분 수열의 수

이렇게 점화식을 세우고 s1[i] == s2[j]일 때 즉 문자열 끝의 두 문자가 같을 때 이전 LCS에서 +1해주면 됨 

예를 들어)

* 문자열의 끝이 같은 경우

CAB DCB => 이런 경우 두 문자열 끝이  B로 같으므로 CA와 DC를 비교하여 저장한 DP값에서 +1을 해주면 됨

* 문자열 끝이 다른 경우

BAC DCB => 이런 경우 두 문자열 끝이 다르다. 가장 긴 부분 수열의 값을 구해야하므로, BAC 와 DC / DCB 와 BA를 비교하여 저장한 DP값을 비교하여 두값 중 큰 값을 저장 하면 된다.

 

코드 : 

#include <iostream>
#include <algorithm>
#include <string>
#define endl '\n'
using namespace std;
string s1, s2;
char c1[1002];
char c2[1002];
int dp[1002][1002];


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

	for (int i = 0; i < s1.size(); i++) {
		c1[i] = s1[i];
	}
	for (int i = 0; i < s2.size(); i++) {
		c2[i] = s2[i];
	}

	for (int i = 1; i <= s1.size(); i++) {
		for (int j = 1; j <= s2.size(); j++) {
			if (c1[i-1] == c2[j-1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

	cout << dp[s1.size()][s2.size()] << endl;
}