[백준][C++] 9251번: LCS <189>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

9251번: LCS

생각의 흐름

이 문제는 두 개의 문자열이 주어졌을 때, 최장 공통 부분 수열(Longest Common Subsequence)을 찾는 문제이다.

 

마지막 글자를 비교한다고 생각하면서 풀면 편하다.

두 문자열 "ABCDE"와 "ABDHE"를 생각해 보자.

 

위 경우처럼 두 문자열의 마지막문자가 같은 경우에는

두 문자열의 LSC는 "ABCD" 와 "ABDH"의 공통수열의 길이 + 1을 하면된다.

즉, DP[i][j] 는 DP[i-1][j-1]+1 이 되는 것 이다.

 

마지막 문자가 다른경우, 기존의 DP[i-1][j] 와 DP[i][j-1]중 더 큰값을 저달받게 된다.

1. 만약 비교하고 있는 문자가 같다면, 이전 까지의 LCS에서 +1을 해주면 된다 !

2. 만약 비교하고 있는 문자가 다르다면, 이전 까지의 LCS에서 각각의 문자를 넣었을 때의 더 큰 값으로 LCS값을 갱신해준다 !

(참고로 문자열의 인덱스는 0번부터 시작하기 때문에 a[i-1] == b[i-1]과 같이 비교하게 됩니다.)

 

 

생각의 흐름

#include <bits/stdc++.h>
using namespace std;
#define MAX 1001

string a, b;
int DP[MAX][MAX];

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

    cin >> a >> b;

    int alen = a.length();
    int blen = b.length();

    for (int i = 1; i <= alen; i++) {
        for (int j = 1; j <= blen; 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]);
            }
        }
    }

    cout << DP[alen][blen] << "\n";

    return 0;
}