백준 9251 c++ -[PlusUltraCode]

[필자 사고] 

문제를 해석해보면 LCS 알고리즘을 사용해야 한다.

LCS 알고리즘은 공부해두면 쉽게 풀 수 있는 문제이다.

 

1. 각 글자들을 비교한다.

2. 만약 각 단어가 다르다면 왼쪽 or 위쪽 중 큰 값을 저장한다..

3. 만약 각 단어가 같다면 왼쪽 대각선의 값에서 +1을 더한다

 

[소스 코드]

 

 

 

 

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

string str1, str2;
int Arr[1001][1001] = { 0 };


void Input() {
	cin >> str1 >> str2;
	for (int i = 0; i < str1.size(); i++) {
		for (int k = 0; k < str2.size(); k++) {
			if (str1[i] == str2[k]) {
				Arr[i + 1][k + 1] = Arr[i][k] + 1;
			}
			else {
				Arr[i + 1][k + 1] = max(Arr[i + 1][k], Arr[i][k + 1]);
			}
		}
	}
	cout << Arr[str1.size()][str2.size()];
}

int main(void) {
	Input();
}