[BOJ] 9251번 LCS (C++)

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

9251번: LCS

 

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

int dp[1001][1001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	string s1, s2;
	cin >> s1 >> s2;
	
	int s1_size = s1.length();
	int s2_size = s2.length();

	for(int i = 1; i <= s1_size; i++){
		for(int j = 1; j <= s2_size; j++){
			if(s1[i - 1] == s2[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;
	return 0;
}

 

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

위와 같은 표를 그려서 풀 수 있다.

 

첫 라인은 전부 0으로 채워주고 다음 줄부터 차례대로 값을 채워나가는데, 규칙은 다음과 같다.

만약, 비교하는 위치의 문자가 서로 같으면

    현재 위치 값 = 왼쪽 대각선 값 + 1

다르다면

    현재 위치 값 = MAX{ 왼쪽 값, 위쪽 값 }

 

표를 읽는 방법은 행에서 현재까지 나온 문자열과 열에서 현재까지 나온 문자열 사이의 LCS 길이이다.

따라서 LCS 길이는 4가 된다.