[백준/C++] 9251번: LCS

문제

풀이

두 수열의 부분 수열 중 가장 긴 공통 부분 수열을 찾는 문제이다.

2차원 배열의 행과 열을 각각의 수열로 생각하고 배열을 읽어 나간다.

문자열1[i]와 문자열2[j]가 같다면 i와 j 모두 증가시키고, LCS의 길이를 1 증가 시킨다.

다르다면 지금까지 가장 큰 LCS의 길이를 가져온다.

배열의 인덱스를 벗어나는걸 방지하려고 i와 j를 1부터 시작했고, 그래서 A[i] == B[j]가 아닌 A[i - 1] == B[j -1]이라고 작성하였다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

string A, B;
int arr[1001][1001];

int main() {

	cin >> A >> B;
	
	for (int i = 1; i <= A.size(); i++) {
		for (int j = 1; j <= B.size(); j++) {
			if (A[i - 1] == B[j - 1]) arr[i][j] = arr[i - 1][j - 1] + 1;
			else arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
		}
	}

	cout << arr[A.size()][B.size()];

	return 0;
}