[백준] 9252번 LCS2

9252 LCS2

문제

---

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

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

입력

---

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

출력

---

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

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

---

풀이)

딱히 설명할 것이 없다. LCS알고리즘을 이용해 푼 간단한 문제이다.

코드)

#include <stdio.h>
#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
string f, s;
int dp[1001][1001];
 
int main() {
    cin >> f >> s;
    // 첫번째행과 첫번째열이 0이여야하니깐 계산상 편의를 위해 문자열 앞에 의미없는 걸 붙여둔다.
    f.insert(f.begin(), '0'); 
    s.insert(s.begin(), '0');
    //1. 테이블 채우기
    for (int i = 1; i < f.length(); i++) {
        for (int j = 1; j < s.length(); j++) {
            if (f[i] == s[j]) { // 문자가 같다면, 왼쪽 대각선 값 + 1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {//문자가 다르면, 왼쪽과 위쪽 값 중 큰 값
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    printf("%d\n", dp[f.length()-1][s.length()-1]);
    vector <char> temp;
    //2. 문자열 구하기
    int i = f.length() - 1;
    int j = s.length() - 1;
    while (dp[i][j] != 0) {
        //같은 숫자있다면 이동
        if (dp[i][j] == dp[i][j - 1]) {
            j -= 1;
        }
        else if (dp[i][j] == dp[i - 1][j]) {
            i -= 1;
        }
        else if (dp[i][j] == dp[i - 1][j - 1] + 1) {
            temp.insert(temp.begin(),f[i]); //거꾸로 삽입되지 않기 위해, 처음에 계속 삽입
            i -= 1;
            j -= 1;
 
        }
    }
    for (int i = 0; i < temp.size(); i++) {
        printf("%c", temp[i]);
    }
 
    return 0;
}

결과)