[백준 / BOJ] C++ 1958 LCS 3

1958번: LCS 3

 

문제

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

1958번: LCS 3

 

 

풀이

9251번 LCS의 확장 버전이다. 아래 문제와 다른 점은 문자열 두개가 아닌 세 개를 비교하는 문제다. 

 https://khyunx.tistory.com/57

[백준 / BOJ] C++ 9251 LCS

2차원 배열을 3차원 배열로 바꾸면 끝이다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string a, b, c;
  cin >> a >> b >> c;
  int dp[101][101][101] = {0};
  int a_size = a.size();
  int b_size = b.size();
  int c_size = c.size();
  for (int i = 1; i <= a_size; i++)
    for (int j = 1; j <= b_size; j++)
      for (int k = 1; k <= c_size; k++)
        if (a[i - 1] == b[j - 1] && b[j - 1] == c[k - 1])
          dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
        else
          dp[i][j][k] = max(max(dp[i - 1][j][k], dp[i][j - 1][k]), dp[i][j][k - 1]);
  cout << dp[a_size][b_size][c_size];
  return 0;
}