(BOJ) 9251 LCS

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

 

문제풀이:

ex) ACAYKP CAPCAK

		A	C	A	Y	K	P
	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	1	2	2	3
C	0	1	2	2	2	2	2
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

=> 답: 4

행과 열의 첫 줄을 0으로 해둠

같은 문자를 만나면 대각선, 즉, 현재 (x,y)라면 (x-1,y-1) 값 +1 해준다 // arr[x][y]=arr[x-1][y-1]+1;

다른 문자를 만다면 자신의 왼쪽이나 위쪽 값 중 큰 값을 넣어줌 // arr[x][y]=max(arr[x][y-1],arr[x-1][y]);

가장 큰 값이 결과값이다.

 

소스 코드:

string s1, s2;
int arr[1001][1001];

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


	cin >> s1 >> s2;

	int len1 = s1.size();
	int len2 = s2.size();
	for (int i = 0; i < len1; i++) {
		for (int j = 0; j <len2; j++) {
			if (s1[i] == s2[j]) {
				arr[i + 1][j + 1] = arr[i][j] + 1;
			}
			else {
				arr[i + 1][j + 1] = max(arr[i][j+1],arr[i+1][j]);
			}
		}
	}
	cout << arr[len1][len2] << '\n';
	return 0;
}