뚝딱뚝딱

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

💡 LCS

✅ 문제 풀이

• 문자열에서 최장 부분 수열의 크기를 찾는 문제
• DP를 이용하여 풀 수 있다.
• dp 배열의 크기는 두 문자열 각각의 크기에 +1 한 만큼으로 행과 열 크기를 배정해준다.
• 행 열 인덱스 0은 모두 0으로 초기화하여 사용할 것이다.
• 그리고 dp 크기만큼 2중 for문을 순회하는데, 각 칸의 값은 해당 칸의 행과 열 알파벳이 동일하면 왼쪽 대각선 위 값에 +1 한 값이고, 다르면 왼쪽과 위에서 오는 값 중 더 큰 값으로 가지게 된다.
  => 이는 표를 그려보면 규칙을 통해 발견할 수 있다.
• 따라서 이를 점화식으로 나타내면 다음과 같다.
  dp[i + 1][j + 1] = dp[i][j] + 1 (행 알파벳=열 알파벳)
  dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) (행 알파벳 =/= 열 알파벳)
  
  
• 그리고 dp[r][c] 즉, 가장 오른쪽 아래에 있는 값이 최종 답이 된다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

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

	string str1, str2;

	cin >> str1 >> str2;

	int r = str1.length();
	int c = str2.length();

	vector<vector<int>> dp(r+1, vector<int>(c+1,0));
	
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int m = max(dp[i][j + 1], dp[i + 1][j]);
			if (str1[i] == str2[j]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			else {
				dp[i + 1][j + 1] = m;
			}
		}
	}

	cout << dp[r][c];
	
	return 0;
}