[C++] 백준 9251번 : LCS

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

9251번: LCS

---

문제 풀이

 10844번:쉬운 계단 수와 문제와 비슷한 문제이다.

2차원 배열 DP[i][j]는 첫 번째 문자(str1)의 i번째와 두 번째 문자(str2)의 j번째까지 가장 긴 부분 수열의 길이를 저장한다.

즉, DP[2][3]은 AC와 CAP를 비교했을 때의 LCS의 길이가 1이라는 것이다. (ex. DP[4][5] == 2)

배열 DP의 원소를 채우면 다음과 같다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

점화식으로 표현하면

str1[i]와 str2[j]가 같다면 DP[i][j] = DP[i-1][j-1] + 1

다르다면 DP[i-1][j]와 DP[i][j-1] 중에서 더 큰 값을 저장하면 된다.

느낀 점

 처음에 어떻게 할지 전혀 방향을 못 잡아서 다른 분들의 코드를 참고했다. 역시 DP의 활용도는 무궁무진한 것 같다. 다행히도 한 번 보고 전에 풀었던 문제와 비슷해서 금방 이해했다.

코드

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

string str1, str2;
int dp[1001][1001];

int main() {
	cin >> str1 >> str2;
	for (int i = 1; i <= str1.size();i++) {
		for (int j = 1; j <= str2.size(); j++) {
			if (str1[i - 1] == str2[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[str1.size()][str2.size()];
}