백준 9251 Lcs

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

---

 

dp배열을 사용해 풀이한다. 문자열 a b가 주어졌을때 a의 인덱스를 s, b 의 인덱스를 t라 한다.

dp[s][t]인 이차원 배열을 사용하는데, 저장되는 값은 각 문자열의 끝을 a[s]와 b[t]라 했을 때 공통되는 부분수열의 최대 길이이다.

 a[s]==b[t]인 경우에는 무조건 부분수열의 길이가 길어지는게 이득이다. 

 

따라서 이 경우에는 dp[s][t] =dp[s-1][t-1]+1 

같지 않은 경우에는 dp[s][t]=max(dp[s-1][t],dp[s][t-1])로 업데이트 시킨다.

 

 

 

 

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

int main() {
	ios::sync_with_stdio(0);

	string a;
	string b;

	cin >> a;
	cin >> b;

	int s = a.size();
	int t = b.size();

	vector<vector<int>>dp(s+1,vector<int>(t+1,0));

	for (int i = 0; i < s; i++) {
		for (int j = 0; j < t; j++) {
			if (a[i] == b[j]) {
				dp[i+1][j+1] = dp[i][j] + 1;
			}
			else 
				dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
		}
	}

	cout << dp[s][t];
	return 0;

}