Baekjoon 9252 LCS 2

목차

[TOC]

문제 설명

image

  • LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
  • 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

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

출력

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

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

    image

풀이 방법

  • LCS 1 문제를 풀었다면 손쉽게 풀 수 있는 문제이다. 기억이 나지 않는다면, 게시된 9251 설명 글을 읽어보면 이해하기 쉬울 것이다.
  • 추가적으로, LCS를 string으로 출력해주어야 하기 때문에, dp 정수 배열과, lcs 스트링 배열을 선언해주어 동적 계획법으로 최장 공통 부분 수열과 그 수열의 길이를 각각 저장해준다.
  • 아래의 설명은 LCS 1 문제에서 설명한 내용을 별도로 가져온 것이다.
  • 예제에서 주어진 ACAYKP 와 CAPCAK를 예로 하면, 첫 입력인 ACAYKP에서 A를 먼저 고르고 CAPCAK의 왼쪽에서부터 하나씩 A와 일치하는지 비교하고, 다음은 C를 고르고 CAPCAK의 왼쪽에서부터 하나씩 C와 일치하는지를 비교하는 식으로, 연속해서 일치하는 횟수를 dp라는 배열에 저장하는 것을 반복한다.
  • 다시 말해, 주어진 예제의 입력들을 string 타입의 s1, s2로 각각 선언해주고, s1의 길이 만큼, 그리고 s2의 길이 만큼의 2중 for문을 돌면서 s1과 s2가 같아지는 시점에서 현재 dp값에서 +1 한 값을 다음 인덱스의 dp에 저장해주고, s1과 s2가 다를 때에는, 인접하는 이전 인덱스의 값들의 최대값으로 갱신하도록 해준다.
  • 그렇게 생성된 dp배열의 마지막 인덱스가 답이 된다.
  • 두 문자열을 문자 하나씩 비교해 나가는 도중, 그 문자가 현재의 lcs에서 더해주면 된다.
  • 그렇지 않다면, 현재 비교하는 인덱스 기준으로 바로 이전의 두 가지 경우에서 더 길이가 긴 경우를 기억한다.
  • 예제에서 주어진 ACAYKP와 CAPCAK를 비교하는 과정 중에서 lcs [3] [3]에는 lcs [2] [3]과 lcs [3] [2] 둘 중 max인 값을 저장된다.
  • 그러면, lcs [3] [3]에는 ACAYKP와 CAPCAK에서 각각 4번째 위치한 Y와 C를 비교할 당시까지의 최선의 답이 저장되는 것이다.

​

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

#define endl '\n'
using namespace std;

//  백준 9252번: LCS 2 (Longest Common Subsequence, 최장 공통 부분 수열)

int dp[1001][1001];
string lcs[1001][1001];

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

    string s1, s2;
    cin >> s1 >> s2;

    for (int i = 0; i < s1.length(); i++) {

        for (int j = 0; j < s2.length(); j++) {

            if (s1[i] == s2[j]) {

                dp[i+1][j+1] = dp[i][j] + 1;
                lcs[i+1][j+1] += lcs[i][j] + s1[i];
            }
            else {

                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);

                if (lcs[i][j+1].length() > lcs[i+1][j].length())
                    lcs[i+1][j+1] = lcs[i][j+1];

                else
                    lcs[i+1][j+1] = lcs[i+1][j];
            }
        }
    }

    cout << dp[s1.length()][s2.length()] << endl;
    cout << lcs[s1.length()][s2.length()] << endl;

    return 0;
}