백준 9251 LCS

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char s1_arr[1001];
char s2_arr[1001];
int memo[1001][1001];

int main() {
	cin >> s1_arr >> s2_arr;
	int s1Size = strlen(s1_arr);
	int s2Size = strlen(s2_arr);
	for (int i = 1; i <= s1Size; i++) {
		for (int j = 1; j <= s2Size; j++) {
			if (s1_arr[i - 1] == s2_arr[j - 1]) {
				memo[i][j] = memo[i - 1][j - 1] + 1;
			}
			else {
				memo[i][j] = max(memo[i][j - 1], memo[i - 1][j]);
			}
		}
	}
	cout << memo[s1Size][s2Size] << endl;
	return 0;

}

DP의 전통스런 문제인 LCS, 최장공통부분수열을 찾는 문제이다.

일단 어떻게 풀지 두시간쯤 끄적여봤는데

도~저히 내 멍청한 머리로는 못 풀 문제 같아서ㅋㅋㅋㅋㅋㅋㅋ

포기하고 결국 구글링했다.

분명 예전에 본거 같은데 왜 기억이 안날까..

구글링해서 대충 위키를 보니 그제서야 예전에 본 기억이 딱 났다.

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4#cite_ref-1

풀이는 간단한데, 아이디어가 너무 어려운 문제..

DP[i][j] = if(X[i] == Y[i]) : DP[i-1][j-1] + 1

 else               max(DP[i-1][j] , DP[i][j-1])

X와 Y는 문자열 두개를 뜻하고 X[i]는 X의 i번째 문자를 뜻함.