[백준 1958] LCS 3

문제 링크 => 1958번: LCS 3 (acmicpc.net)

1958번: LCS 3

 

다이나믹 프로그래밍 문제이다.

 

알고리즘 수업때 배웠던 LCS 에서 문자열이 하나 더 추가되어 총 3개의 문자열의 LCS를 구해야 한다.

 

문자열 X, Y, Z 가 있다고 할 때 Optimal Substructure은 다음과 같다.

 

이때 LCS(X, Y, Z) 를 X, Y, Z 문자열들의 Longest Common Subsequence 값이라고 할 때,

 

Xn == Yn == Zn 일 경우

   => LCS(Xn, Yn, Zn) = LCS(Xn-1, Yn-1, Zn-1) + 1

 

Xn == Yn == Zn 가 아닌 경우

   => LCS(Xn, Yn, Zn) = max({LCS(Xn, Yn, Zn-1), LCS(Xn, Yn-1, Zn), LCS(Xn-1, Yn, Zn)

                                       , LCS(Xn, Yn-1, Zn-1), LCS(Xn-1, Yn, Zn-1), LCS(Xn-1, Yn-1, Zn)})

 

위를 top-down 식으로 구현할 경우 memoziation 을 사용해야 되는데 이렇게 풀면 overlapping subprogram 이 많이 생겨나서 시간 초과가 뜬다.

 

따라서 bottom-up 방식으로 구현하면 된다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

string X, Y, Z;
int d[101][101][101];

int LCS(int nx, int ny, int nz) 
{
	for (int i = 1; i <= nx; i++) {
		for (int j = 1; j <= ny; j++) {
			for (int k = 1; k <= nz; k++) {
				if (X[i - 1] == Y[j - 1] && X[i - 1] == Z[k - 1] && Y[j - 1] == Z[k - 1])
					d[i][j][k] = d[i - 1][j - 1][k - 1] + 1;
				else {
					int maxLCS = max({ d[i][j][k - 1],d[i][j - 1][k],d[i - 1][j][k],
						d[i][j - 1][k - 1],d[i - 1][j][k - 1],d[i - 1][j - 1][k] });
					if (d[i][j][k] < maxLCS)
						d[i][j][k] = maxLCS;
				}
			}
		}
	}

	return d[nx][ny][nz];
}

int main(void) 
{
	cin >> X >> Y >> Z;
	cout << LCS(X.size(), Y.size(), Z.size());

	return 0;
}