[백준 1958번] LCS 3 (C++)

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

1958번: LCS 3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int dp[101][101][101];
string s1, s2, s3;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> s1 >> s2 >> s3;

    for(int i=1; i<=s1.size(); i++)
    {
        for(int j=1; j<=s2.size(); j++)
        {
            for(int k=1; k<=s3.size(); k++)
            {
                if(s1[i-1]==s2[j-1] && s2[j-1]==s3[k-1]) //3개 문자가 모두 같은 경우
                {
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 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[s1.size()][s2.size()][s3.size()];
}

 

문제풀이 참고 링크 : https://blob-thinking.tistory.com/270

[백준 9252번] LCS 2 (C++)

 

기존 LCS 문제에서 문자열의 갯수가 늘어난 문제이다.

dp 배열이 확장된 것을 제외하면 사실상 로직은 동일하다.

 

처음에 LCS를 2번 (s1, s2 / s2, s3) 돌리는 방식으로 풀다가 잘 안되어서 찾아보니 문자열의 길이가 100이라 3중 for문으로 풀린다는 것을 알았다.