백준 9251 - LCS(C++)

문제 링크입니다. https://www.acmicpc.net/problem/9251

9251번: LCS

두 문자열이 주어졌을때, 공통되는 가장 긴 수열을 찾는 문제입니다.

이 문제의 핵심은 연속된 문자열이 아닌 부분 수열이라는 점입니다.

따라서 X, Y 문자열을 하나하나 비교해나가면서 최댓값을 확인하면 됩니다.

 

그림으로 한번 확인해보겠습니다.

 

X, Y 문자열이 주어졌을때, 두 문자열 중 하나를 고정시킵니다.

X 문자열을 고정했다고 했을때, Y 문자열을 1개부터 문자열의 크기까지 문자열을 늘려가면서 X 문자열과 비교합니다.

상, 좌, 대각선 좌 와 값을 비교하면서 큰 값을 들고옵니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>

using namespace std;

string X, Y;
int dp[1001][1001];

int Max(int x, int y, int z, bool add) {
	int ans = 0;
	if (add) {
		ans = max(x, y);
		ans = max(ans, z + 1);
	}
	else {
		ans = max(x, y);
		ans = max(ans, z);
	}
	return ans;
}

void solve() {
	for (int i = 1; i <= X.size(); i++) {
		for (int j = 1; j <= Y.size(); j++) {
			if(X[i-1] == Y[j-1]) dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] , true);
			else dp[i][j] = Max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1], false);
		}
	}
	cout << dp[X.size()][Y.size()];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> X >> Y;
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요