[백준] 9252번 : LCS 2 - C++ / JAVA

백준 9252 : LCS 2

등급 : Gold IV

9252번: LCS 2 (acmicpc.net)

9252번: LCS 2

사용 알고리즘 : Dynamic Programming

사용 자료구조 : -

 

다이나믹 프로그래밍으로 풀 수 있는 고전적인 문제이다.

배열의 가장 첫 부분을 비우고, 두 글자가 같은 부분이 나오면, 이전까지 같은 부분이 있었는지 확인해 + 1을 해준다.

→ str1[i] == str2[j]이면, dp[i][j] = dp[i-1][j-1] + 1.

     (ACA와 CA의 경우 A를 제외하고 AC와 C 중 이전까지 일치한 길이 1. ∴ 현재 위치 일치 갯수 = 2 )

 

두 글자가 같지 않다면, 이전 글자를 확인하여 더 큰 값을 가져오도록 한다.

→ str[i] != str[j]이면, dp[i][j] = max(dp[i][j-1], dp[i-1][j])

이와 같은 방식으로 진행하면, 위와 같은 DP 배열이 완성된다.

즉, 최대 길이는 DP배열의 끝 값인 4가 된다.

또한 최대 길이에 해당하는 문자는 가장 끝부터 검색하여 서로 문자가 다르면 인덱스가 더 작은 같은 값인 곳으로, 

서로 문자가 같다면 대각선으로 이동하게 구현해주고, 역순으로 출력하면 된다.

( 위의 경우 K, A, C, A순으로 결과값 저장. 이후 역순인 ACAK로 출력 )

<hide/>
#include <iostream>
#include <algorithm>

using namespace std;

int dp[1001][1001] = { 0 };

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

    string x, y;
    cin >> x >> y;

    int n = x.size();
    int m = y.size();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (x[i - 1] == y[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[x.size()][y.size()] << "\n";

    string str = "";
    while (dp[n][m] != 0)
    {
        if (dp[n][m] == dp[n - 1][m]) n--;
        else if (dp[n][m] == dp[n][m - 1]) m--;
        else
        {
            str += x[n - 1];
            n--; m--;
        }
    }
    reverse(str.begin(), str.end());
    cout << str;
}

<hide/>
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        int[][] dp = new int[1001][1001];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringBuffer sbf = new StringBuffer();
        String x = br.readLine();
        String y = br.readLine();
        int n = x.length();
        int m = y.length();

        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(x.charAt(i-1) == y.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        sb.append(dp[n][m]).append("\n");

        while(dp[n][m] != 0)
        {
            if(dp[n][m] == dp[n-1][m]) n--;
            else if(dp[n][m] == dp[n][m-1]) m--;
            else
            {
                sbf.append(x.charAt(n-1));
                n--; m--;
            }
        }
        sbf.reverse();
        sb.append(sbf);
        System.out.println(sb);
    }
}