[BOJ 백준] 9251번 LCS

문제

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

9251번: LCS

접근

 DP를 통해 문제를 해결하였다. 입력받은 두 문자열 s1, s2에서 각자 한 문자씩 가리키는 포인터 p1, p2를 통해 s1[p1]과 s2[p2]가 같다면 LCS의 길이를 늘여주기 위해 1을 더하고, 같지 않다면 p1을 한 칸 앞으로 전진하거나(rec(p1 + 1, p2)), p2를 한 칸 앞으로 전진시킨 경우(rec(p1, p2 + 1)) 중 더 큰 값(max)을 선택하면 된다. 이 과정을 재귀를 통해 구현하였다. 즉, 탑다운(top-down) 방식을 통해 DP를 구현하였다. 

 

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

string s1, s2;
int dp[1005][1005] = {0};
int rec(int p1, int p2){
    if (p1 >= s1.size() || p2 >= s2.size())
        return 0;
    if (dp[p1][p2] != -1)
        return dp[p1][p2];
    if (s1[p1] == s2[p2])
        return dp[p1][p2] = 1 + rec(p1 + 1, p2 + 1);
    else
        return dp[p1][p2] = max(rec(p1 + 1, p2), rec(p1, p2 + 1));
}

int main() {
    cin >> s1 >> s2;
    for (int i = 0; i < s1.size(); i++) {
        for (int j = 0; j < s2.size(); j++)
            dp[i][j] = -1;
    }
    cout << rec(0, 0);
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study