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

문제 링크

1958번 - LCS 3

설명

길이가 100 이하인 소문자 문자열 3개가 주어질 때, 세 문자열의 최장 공통 부분수열(LCS) 길이를 구하는 문제입니다.

접근법

먼저, 두 문자열의 LCS를 구하는 2차원 DP를 세 문자열로 확장합니다. 세 문자열 각각의 현재 위치를 나타내는 세 개의 인덱스를 사용하여 3차원 DP를 구성합니다.

다음으로, 세 문자열의 현재 문자가 모두 같으면 이전 상태에서 1을 더합니다. 그렇지 않으면 세 문자열 중 하나의 인덱스를 줄인 상태들 중 최댓값을 선택합니다.

이후, 모든 인덱스 조합에 대해 계산을 완료하면 세 문자열의 끝까지 고려했을 때의 값이 답이 됩니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var A = Console.ReadLine()!;
      var B = Console.ReadLine()!;
      var C = Console.ReadLine()!;

      var a = A.Length;
      var b = B.Length;
      var c = C.Length;
      var dp = new int[a + 1, b + 1, c + 1];

      for (var i = 1; i <= a; i++) {
        for (var j = 1; j <= b; j++) {
          for (var k = 1; k <= c; k++) {
            if (A[i - 1] == B[j - 1] && A[i - 1] == C[k - 1])
              dp[i, j, k] = dp[i - 1, j - 1, k - 1] + 1;
            else {
              var mx = dp[i - 1, j, k];
              if (dp[i, j - 1, k] > mx)
                mx = dp[i, j - 1, k];
              if (dp[i, j, k - 1] > mx)
                mx = dp[i, j, k - 1];
              dp[i, j, k] = mx;
            }
          }
        }
      }

      Console.WriteLine(dp[a, b, c]);
    }
  }
}

C++

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

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

  string A, B, C;
  cin >> A >> B >> C;
  int a = A.size(), b = B.size(), c = C.size();

  static int dp[101][101][101];

  for (int i = 1; i <= a; i++) {
    for (int j = 1; j <= b; j++) {
      for (int k = 1; k <= c; k++) {
        if (A[i - 1] == B[j - 1] && A[i - 1] == C[k - 1])
          dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
        else
          dp[i][j][k] = max({dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1]});
      }
    }
  }

  cout << dp[a][b][c] << "\n";

  return 0;
}