백준 9252 - LCS 2(C++, 복습)

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

9252번: LCS 2

LCS를 사용한 문제입니다.

해당 문제에서 변형된 문제이니, 문제를 풀고 와주시면 좋을거 같습니다. ->  https://junseok.tistory.com/170

 

 

LCS 문제에서 추가된 것은 수열까지 출력하는 것입니다.

쉽게 생각할 수 있는 방법은 수열을 저장하면서 푸는 방법인데 이는 시간초과로 실패했습니다.

 

따라서 역추적을 하는 방법을 이용했습니다.

dp 배열의 (X.size(), Y.size())에는 구할 수 있는 가장 긴 수열의 길이가 저장되어 있습니다.

(X, Y)의 값을 얻었을 때, 비교했던 위치를 살펴보면, (X-1, Y) / (X, Y-1) / (X-1, Y-1) 입니다.

그렇다면 3개의 값을 비교하면서 큰 값으로 돌아간다면, 원하는 수열을 찾을 수 있을 것입니다.

이때, 찾으려는 위치에서 수열의 값이 같다면, (X-1, Y-1)로 돌아가야 합니다. 

 

 

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

#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 print(int x, int y){
    if(dp[x][y] == 0) return;
    if(X[x-1] == Y[y-1]){
        print(x-1, y-1);
        cout << X[x-1];
    }
    else dp[x-1][y] > dp[x][y-1] ? print(x-1,y):print(x,y-1);
}

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()] << "\n";
	print(X.size(), Y.size());
}

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

 

 

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