[C++] BOJ 9251 / DP (LCS 최장 공통 부분 수열)

코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int same[1002][1002];

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

    string a, b;
    cin >> a >> b;
    int lenA = a.size();
    int lenB = b.size();
    for(int curA=1;curA<=lenA;curA++) {
        for(int curB=1;curB<=lenB;curB++) {
            if(a[curA-1] == b[curB-1]) {
                same[curA][curB] = same[curA-1][curB-1] + 1; 
            }else if(a[curA-1] != b[curB-1]) {
                same[curA][curB] = max(same[curA-1][curB], same[curA][curB-1]);
            }
        }
    }
    cout << same[lenA][lenB];
}

 

코드 분석

어려워보이지만 두가지 경우로 나눠서 진행하면 쉽다.

이중 for문을 통해 한글자 씩 비교하면서 같은 경우와 다른 경우에 따른 점화식을 세우면 된다.

 

점화식

문자가 같을 경우 => same[curA][curB] = same[curA-1][curB-1] + 1

문자가 다를 경우 => same[curA][curB] = max(same[curA-1][curB], same[curA][curB-1])