[백준 9251] LCS (C#, C++) - soo:bak

문제 링크

9251번 - LCS

설명

두 문자열이 주어지는 상황에서 각 문자열의 길이 (최대 1000)가 주어질 때, 두 문자열의 최장 공통 부분 수열(LCS)의 길이를 구하는 문제입니다.

부분 수열은 원래 문자열에서 일부 문자를 제거하여 만든 수열이고, 공통 부분 수열은 두 문자열 모두의 부분 수열인 것을 의미합니다.

접근법

모든 부분 수열을 확인하면 시간 초과가 발생하므로 동적 프로그래밍을 사용합니다.

dp[i][j]를 첫 번째 문자열의 처음 i개 문자와 두 번째 문자열의 처음 j개 문자까지 고려했을 때의 LCS 길이로 정의합니다. i번째와 j번째 문자가 같으면 이전 상태에서 1을 더하고, 다르면 둘 중 하나를 제외한 경우의 최댓값을 선택합니다.

예를 들어 “ACAYKP”와 “CAPCAK”의 LCS를 구할 때:

• A(1)와 C(1): 다름 → max(dp[0][1], dp[1][0]) = 0
• A(1)와 A(2): 같음 → dp[0][1] + 1 = 1
• ACA(3)와 CA(2): A(3)와 A(2) 같음 → dp[2][1] + 1 = 2
• ACAY(4)와 CAP(3): Y와 P 다름 → max(dp[3][3], dp[4][2]) = 2
• ACAYKP(6)와 CAPCAK(6): 최종 LCS 길이 = 4 (“ACAK”)

모든 i (1~길이1)와 j (1~길이2)를 채운 후 dp[길이1][길이2]가 답입니다. 시간 복잡도는 O(N×M)입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var s1 = Console.ReadLine()!;
      var s2 = Console.ReadLine()!;
      var n = s1.Length;
      var m = s2.Length;

      var dp = new int[n + 1, m + 1];

      for (var i = 1; i <= n; i++) {
        for (var j = 1; j <= m; j++) {
          if (s1[i - 1] == s2[j - 1])
            dp[i, j] = dp[i - 1, j - 1] + 1;
          else
            dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
        }
      }

      Console.WriteLine(dp[n, m]);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string a, b; cin >> a >> b;
  int n = a.size(), m = b.size();

  vvi dp(n + 1, vi(m + 1, 0));

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

  cout << dp[n][m] << "\n";

  return 0;
}