[C/C++] 백준 9252번

https://www.acmicpc.net/problem/9252

 

안녕하세요

오늘 풀어볼 문제는 백준 9252번, 골드 4번 문제입니다.

 

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

 

조건

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

 

아이디어

• DP 배열 정의:
  • dp[i][j]: A[1…i]A[1 \ldots i]A[1…i]와 B[1…j]B[1 \ldots j]B[1…j]의 LCS 길이.
• 점화식:
  • A[i]==B[j]일 경우:
    • dp[i][j]=dp[i−1][j−1]+1
  • A[i]!=B[j]일 경우
    • dp[i][j]=max(dp[i−1][j],dp[i][j−1])
• 수열 복원:
  • dp 배열을 역추적하여 LCS 문자열을 복원.
• 초기값:
  • dp[i][0]=dp[0][j]=0:
    • 빈 문자열과의 LCS 길이는 항상 0

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    string A, B;
    cin >> A >> B;

    int n = A.size();
    int m = B.size();

    // dp 배열 초기화
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    //dp 점화식 계산
    for(int i=1; i<=n; i++){
        for(int j =1; j<=m; j++){
            if(A[i-1] == B[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    // lcs 길이 출력
    cout << dp[n][m]<<"\n";

    if(dp[n][m]!=0){
        //lcs 복원
        string lcs = "";
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (A[i - 1] == B[j - 1]) {
                lcs += A[i - 1]; // 공통 문자를 LCS에 추가
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                i--; // 위쪽으로 이동
            } else {
                j--; // 왼쪽으로 이동
            }
        }

        // LCS 문자열 출력 (역순이므로 뒤집기)
        reverse(lcs.begin(), lcs.end());
        cout << lcs << "\n";
    }

    return 0;
}

 

오늘도 끝