[백준 c++] 9251 LCS (골5)

📌 문제

Longest Common Subsequence, 최장 공통 부분 수열을 구하는 문제다. 이 문제는 직접적으로 문제의 규칙을 알려주지 않지만 암묵적인 규칙이 존재한다.일단 부분 수열을 만들 때 무조건 수열 내 알파벳 순서를 지켜야한다는 점이다.

 

필자는 이 문제가 DP로 풀린다는 것을 알고 있었지만 어떻게 풀어야하지?? 막막했다. 하지만 DP라는 문제를 생각해내면 금방 풀 수 있는 문제다.

 

먼저 문자열 별로 배열을 두 개 작성할 수 있도록 한다. 

 

 

 

💻 정답 코드

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

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//첫째 줄과 둘째 줄에 두 문자열이 주어진다. 
	//문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
	string str1, str2;  cin >> str1 >> str2;
	int M = str1.size();
	int N = str2.size();

	vector<vector<int>> dp(M+1);
	for (int i = 0; i < M + 1; i++) dp[i].resize(N + 1, 0);

	//비교 진행하기
	
	for (int i = 0; i < M ; i++){
		for (int j = 0; j < N ; j++) {

			//같을 경우
			if (str1[i] == str2[j]) dp[i + 1][j + 1] = dp[i][j] + 1;

			//다를 경우
			else dp[i + 1][j + 1] = dp[i][j + 1] > dp[i + 1][j] ? dp[i][j + 1] : dp[i + 1][j];

		}
	}

	cout << dp[M][N] << endl;
	return 0;
}