BOJ-9252-LCS 2

[changicho]

9252. LCS 2

링크

난이도	정답률(_%)
Gold V	42.193

설계

동적 계획법

정리

내 코드 (ms)	빠른 코드 (ms)
652

고생한 점

코드

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

#define MAXSIZE 1001
#define nl "\n"


using namespace std;

int DP[MAXSIZE][MAXSIZE];
string LCS[MAXSIZE][MAXSIZE];

void solution() {
	string A, B;

	cin >> A >> B;

	int A_Size = A.length();
	int B_Size = B.length();

	for (int i = 1; i <= A_Size; i++) {
		for (int j = 1; j <= B_Size; j++) {
			if (A[i - 1] == B[j - 1]) {
				DP[i][j] = DP[i - 1][j - 1] + 1;
				LCS[i][j] = LCS[i][j] + LCS[i - 1][j - 1] + A[i - 1];
			}
			else {
				DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);

				if (LCS[i - 1][j].length() > LCS[i][j - 1].length()) {
					LCS[i][j] = LCS[i - 1][j];
				}
				else {
					LCS[i][j] = LCS[i][j - 1];
				}
			}

		}
	}

	cout << DP[A_Size][B_Size] << nl << LCS[A_Size][B_Size] << nl;
}

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

	solution();

	return 0;
}