[ BOJ 백준 1958번 - LCS 3 ] 해설 및 코드

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

 

 

목적

문자열 3개의 LCS를 구하자.

 

접근법

1. 백준 9252번 - LCS 2의 풀이와 비슷하다. 2차원 배열에서 3차원 배열로 DP를 적용하자.

 

2. s[i][j][k]를 채우는 값은 인접한 7개의 배열 요소의 영향을 받는다.

 

#include<bits/stdc++.h>
#define N 101
using namespace std;
 
char a[N],b[N],c[N];
int s[N][N][N],i,j,k,u,v;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>a>>b>>c;
    for(i=0;a[i];++i)for(j=0;b[j];++j)for(k=0;c[k];++k){
        if(a[i]==b[j]&&b[j]==c[k])s[i+1][j+1][k+1]=s[i][j][k]+1;
        else{
            u=max(s[i+1][j][k],max(s[i][j+1][k],s[i][j][k+1]));
            v=max(s[i+1][j+1][k],max(s[i+1][j][k+1],s[i][j+1][k+1]));
            s[i+1][j+1][k+1]=max(u,v);
        }
    }
    cout<<s[i][j][k];
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.