BOJ 9252. LCS 2

🙇‍♀️[Gold IV] LCS 2 - 9252

문제 링크

성능 요약

메모리: 5984 KB, 시간: 4 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 2월 22일 15:31:44

문제 설명

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

🚀풀이

LCS가 최대 길이만 알 수 있는데 cache값을 바탕으로 값을 역 추적하여 문제를 해결한다.

string str1, str2;
cin >> str1 >> str2;

for (int i = 1; i <= str1.length(); ++i)
{
    for (int j = 1; j <= str2.length(); ++j)
    {
        if (str1[i - 1] == str2[j - 1])
        {
            cache[i][j] = cache[i - 1][j - 1] + 1;
        }
        else
        {
            cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]);
        }
    }
}

cout << cache[str1.length()][str2.length()] << '\n';

이렇게 cache를 채워주고 최대 길이를 구한다.

if (cache[str1.length()][str2.length()] == 0)
    return;
else
{
    int f = str1.length();
    int s = str2.length();
    // 그 수열을 찾아야됨
    string str;

    // 수열을 역 추적하기
    int idx = str2.size();
    for (int i = str1.size(); i > 0; --i)
    {
        for (int j = idx; j > 0; --j)
        {
            if (cache[i][j] == cache[i - 1][j])
            {
                idx = j;
                break;
            }
            else if (cache[i][j] == cache[i][j - 1])
                continue;
            else
                str = str1[i - 1] + str;
        }
    }

    cout << str;
}

cache를 바탕으로 역 추적을 시작하는데

cache는 문제에 예시를 그대로 사용하면 이렇게된다.

이때 4부분부터 값을 가져오는데 cache[i][j] == cache[i - 1][j]라면 idx를 j로 치환.
cache[i][j] == cache[i][j - 1] 라면 그냥 넘기고

최종적으로 그게 아니면 str = str1[i - 1] + str;로 하여 최종 값을 완성한다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// LCS (Longest Common Subsequence) 2

vector<vector<int>> cache(1001, vector<int>(1001));
void LCS()
{
	string str1, str2;
	cin >> str1 >> str2;

	for (int i = 1; i <= str1.length(); ++i)
	{
		for (int j = 1; j <= str2.length(); ++j)
		{
			if (str1[i - 1] == str2[j - 1])
			{
				cache[i][j] = cache[i - 1][j - 1] + 1;
			}
			else
			{
				cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]);
			}
		}
	}

	cout << cache[str1.length()][str2.length()] << '\n';

	if (cache[str1.length()][str2.length()] == 0)
		return;
	else
	{
		int f = str1.length();
		int s = str2.length();
		// 그 수열을 찾아야됨
		string str;

		// 수열을 역 추적하기
		int idx = str2.size();
		for (int i = str1.size(); i > 0; --i)
		{
			for (int j = idx; j > 0; --j)
			{
				if (cache[i][j] == cache[i - 1][j])
				{
					idx = j;
					break;
				}
				else if (cache[i][j] == cache[i][j - 1])
					continue;
				else
					str = str1[i - 1] + str;
			}
		}

		cout << str;
	}
}

void solve()
{
	LCS();
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}