[백준/Baekjoon] 9251 LCS C++ :: Dynamic programming

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

9251번: LCS

---

1. Logic

- 첫번째 문자부터 확인하면서 각 문자열의 끝까지 확인하고 만약 각 인덱스의 서로의 문자가 같으면 값 +1

 

Topdown형식으로 풀었다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int dp[1001][1001];
string str1, str2;

int solve(int s1Idx, int s2Idx) {
    // 기저조건(각 문자열 끝까지 돌면 리턴)
    if(s1Idx == str1.length() || s2Idx == str2.length()) return 0;
    int &ret = dp[s1Idx][s2Idx];

    if(ret != -1) return ret;

    // str1 끝까지 안갔으면 그다음 인덱스의 문자 확인
    if(s1Idx < str1.length()) {
        ret = max(ret, solve(s1Idx + 1, s2Idx));
    }

    // str2 끝까지 안갔으면 그다음 인덱스의 문자 확인
    if(s2Idx < str2.length()) {
        ret = max(ret, solve(s1Idx, s2Idx + 1));
    }

    // 만약 각 인덱스의 문자와 같으면 +1
    if(str1[s1Idx] == str2[s2Idx]) {
        ret = max(ret, solve(s1Idx + 1, s2Idx + 1) + 1);
    }

    return ret;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cin >> str1 >> str2;

    cout << solve(0, 0);
}

 

 

---

3. Feedback

기본적인 DP문제?

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90