[C++] BJO 9251 : LCS

문제

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

 

 

 

 

풀이

dp를 이용하여 푼다.

dp[i][j] : a배열의 i번째 문자, b배열의 j번째 문자까지의 LCS를 저장

 

 

dp 업데이트 방법

1. a[i] == b[j] 인 경우, dp[i][j] = dp[i-1][j-1]+1
2. a[i] == b[j] 여부 상관 없이, 항상 dp[i][j]= max({dp[i][j],   dp[i-1][j],   dp[i][j-1]})

 

 

 

 

코드

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

string a, b;
int dp[1001][1001]; // [a_len][b_len]
int main() {
    cin >> a >> b;
    int a_len = a.size();
    int b_len = b.size();

    for(int i=1; i<=a_len; i++){
        for(int j=1; j<=b_len; j++){
            if(a[i-1] == b[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
            }
            dp[i][j] = max({dp[i][j], dp[i-1][j], dp[i][j-1]});
        }
    }

    cout << dp[a_len][b_len] << "\n";
    return 0;
}

 

 

 

---

메모

2차원 dp 이용하는 문제를 많이 풀어봐야겠다.