[BOJ] LCS(9251)

[백준(BOJ)] LCS(9251) C++

문제 : BOJ_9251번 LCS

문제 설명

DP

최대 1000 글자의 두 단어가 주어지고, 두 단어에서 공통된 부분 수열 중 가장 긴 수열을 찾는 문제입니다.

문제 자체는 간단하지만, 완전 탐색을 이용하면 시간 초과가 나기 때문에 DP를 활용하여 해결해야 하는 문제입니다.

---

Solution

위 표를 참고해서 DP 식을 짜야 합니다.

두 문자열의 길이만큼 2중 for 문을 순회하면서 문자가 같을 때와 다를 때 두 조건으로 dp 식을 세워줍니다.

두 문자열이 같다면, dp[i][j] = dp[i-1][j-1]+1

즉, 위 표에서 대각선의 dp 값 + 1입니다.

두 문자열이 다르다면, dp[i][j] = max(dp[i][j-1], dp[i-1][j])

즉, 위 표에서의 왼쪽이나 위쪽 값의 최댓값입니다.

두 값이 같지 않다면, 그전 dp 값 중 최댓값이 들어가야 하는데, 표의 왼쪽이나 위쪽 값의 최댓값이 그 값이기 때문입니다.

---

Description

• 문자열은 0번 인덱스부터 시작하므로, 이를 처리하기 위해 dp 값은 i와 j에 1씩 더해주었습니다.
• 그러므로 최종 출력값도 dp[1번 문자열의 길이-1][2번 문자열의 길이-1]이 아닌 dp[1번 문자열의 길이][2번 문자열의 길이]입니다.

---

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char str1[1001], str2[1001];
int dp[1001][1001];
int main(void){
    cin >> str1 >> str2;
    for(int i=0; str1[i]!='\0'; i++){
        for(int j=0; str2[j]!='\0'; j++){
            if(str1[i]==str2[j]){
                dp[i+1][j+1]=dp[i][j]+1;
            }
            else {
                dp[i+1][j+1]= max(dp[i][j+1],dp[i+1][j]);
            }
        }
    }
    cout << dp[strlen(str1)][strlen(str2)] << '\n';
    return 0;
}