BOJ 1958번 LCS 3

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

github : https://github.com/junho0956/Algorithm/blob/master/1958/1958/%EC%86%8C%EC%8A%A4.cpp

 

LCS 의 개념을 정리한 포스팅입니다.

LCS : https://junho0956.tistory.com/39?category=868069

 

LCS2보다 오히려 쉬운 문제입니다. LCS의 개념을 안다는 가정하에말이죠

2차원에서 3차원으로 늘어난 것 뿐이고, 3중포문이지만 100*100*100 에 if문 2개는 시간내에 해결가능한 코드입니다.

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int dp[101][101][101];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    string fs, ss, ts;
    cin >> fs >> ss >> ts;
 
    for (int i = 0; i < fs.length(); i++) {
        for (int j = 0; j < ss.length(); j++) {
            for (int k = 0; k < ts.length(); k++) {
                if (fs[i] == ss[j] && ss[j] == ts[k]) dp[i + 1][j + 1][k + 1] = dp[i][j][k] + 1;
                else dp[i + 1][j + 1][k + 1] = max(dp[i][j + 1][k + 1], max(dp[i + 1][j][k + 1], dp[i + 1][j + 1][k]));
            }
        }
    }
 
    cout << dp[fs.length()][ss.length()][ts.length()];
    return 0;
}