💍제출 코드

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

string A, B;   
int DP[1001][1001];

int main(void) {
	cin >> A >> B;

	int lenA = A.length();
	int lenB = B.length();
	
	for (int a = 1; a <= lenA; a++) {
		for (int b = 1; b <= lenB; b++) {
			if (A[a - 1] == B[b - 1])           //A, B는 0부터 채워짐
				DP[a][b] = DP[a - 1][b - 1] + 1;     //DP는 1부터 채움. 0부터 하면 안됨.
			else DP[a][b] = max(DP[a - 1][b], DP[a][b - 1]);
		}
	}

	cout << DP[lenA][lenB] << endl;

	return 0;
}

🙃DP[][]: 거기까지의 공동문자열 개수

이 그림이 DP 테이블을 의미한다.
3은 ACA와 CAPCAK의 공동 문자열 개수이다.

DP[a][b]는 A문자열의 인덱스 a까지, B문자열의 b까지 본 공동문자열 개수가 된다.

if (A[a - 1] == B[b - 1])                 //A, B는 0부터 채워짐
    DP[a][b] = DP[a - 1][b - 1] + 1;     //DP는 1부터 채움. 0부터 하면 안됨.
else DP[a][b] = max(DP[a - 1][b], DP[a][b - 1]);

DP값을 결정하는 이 코드는 사진의 빨간 선과 함께 보면 이해할 수 있다.