[백준 9251] lcs

LCS

문제설명

주어진 두 문자열에서 최장 부분 수열을 구해 출력 시킨다.

알고리즘

1. 값을 각각 입력받고 입력 받은 문자열에 편의를 위해 0을 추가해서 붙인다.
2. 각 첫행 첫열은 0으로 초기화한다.
3. 비교하는 기준 문자열에서 같으면 해당 칸의 대각선 값 +1을 표에 넣는다.
4. 비교하는 기준 문자열에서 다르면 왼쪽, 또는 위의 값 중에 더 큰 값을 찾아서 넣는다.
5. 해당 테이블이 가장 오른쪽 아래 값이 정답이 될 수 있다.

---

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#define MAX 1001
using namespace std;

int lcs[MAX][MAX];

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

    string A,B;

    cin >> A >> B;

    A = '0' + A;
    B = '0' + B;

    int len1 = A.length();
    int len2 = B.length();

    for (int i = 0; i < len1; i++)
    {
        for (int j = 0; j < len2 ;j++)
        {
            if (i == 0 || j == 0)//첫행 첫열은 0으로 초기화
            {
                lcs[i][j] = 0;
                continue;
            }

            if (A[i] == B[j]) //문자열이 같으면 대각선 값 더하기 1  
                lcs[i][j] = lcs[i-1][j-1]+1;
            else//문자열이 다르면 왼쪽 또는 위의 값에서 큰 값 선택 
                lcs[i][j] = max(lcs[i][j - 1],lcs[i-1][j]);
        }
    }

    cout << lcs[len1 - 1][len2 - 1] << "\n";//결과 값 출력 

    return 0;
}

고찰

해당 문제는 다이나믹 프로그래밍 개념을 이용해서 푸는 문제였다. 하지만 개념을 정확하게 이해해야 풀 수 있는 문제였다.
역시 바로 풀리지는 않아서 lcs 알고리즘을 검색해서 다른사람의 표를 이해해서 풀 수 있었다.