백준 9251번 [LCS](C++)-yes6686- 티스토리

백준 문제 풀이: 9251 [LCS]

---

문제 링크: https://www.acmicpc.net/problem/9251

문제 설명:

두 문자열 A와 B가 주어질 때, 두 문자열의 최장 공통 부분 수열 (LCS)의 길이를 구하는 문제입니다. 최장 공통 부분 수열은 두 문자열에서 순서를 유지하며 일부 문자를 선택하여 만들 수 있는 가장 긴 부분 수열입니다.

입력:

• 첫 번째 줄에 문자열 A가 주어집니다.
• 두 번째 줄에 문자열 B가 주어집니다.
• 문자열의 길이는 최대 1,000입니다.

출력:

• 첫 번째 줄에 두 문자열의 LCS 길이를 출력합니다.

---

문제 해결 코드

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

int dp[1001][1001];

int main() {
    string a, b;
    cin >> a >> b;

    // DP 테이블 채우기
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1; // 문자가 같으면 대각선 값 + 1
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 위나 왼쪽 값 중 최대값
            }
        }
    }

    // 결과 출력
    cout << dp[a.length()][b.length()] << '\n';
    return 0;
}

예제

입력:
ACAYKP
CAPCAK

출력:
4

입력:
ABCDEF
ACE

출력:
3

---

코드 설명

• DP 테이블: dp[i][j]는 문자열 A의 처음 i글자와 문자열 B의 처음 j글자 사이의 최장 공통 부분 수열의 길이를 저장합니다.
• 점화식:
  • 문자가 같을 경우: dp[i][j] = dp[i-1][j-1] + 1
  • 문자가 다를 경우: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• 초기화: 첫 행과 첫 열은 모두 0으로 초기화됩니다. 이는 공집합과의 LCS 길이가 항상 0임을 나타냅니다.

시간 복잡도

• 이중 루프를 사용하여 a.length() × b.length()의 DP 테이블을 채우므로 시간 복잡도는 O(n × m)입니다.
• n, m은 최대 1,000이므로 효율적으로 작동합니다.

---

결과

코드는 두 문자열의 최장 공통 부분 수열의 길이를 정확히 계산하며, DP를 이용한 효율적인 접근 방식을 구현합니다. 코드의 시간 복잡도와 공간 복잡도는 문제의 제약을 만족합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!