BOJ 1958 | LCS 3

처음에는 LCS 연산을 2회 해서 해결하려고 했으나 그렇게 만만한 문제는 아니었다.

생각해보면 LCS 연산은 해가 유일한 연산이 아니라서 길이가 같은 다른 해가 나올 수도 있고, 연산하는 방법에 따라서 다른 답이 나올 수 있어서 이렇게는 해결이 불가능하다.

그래서 문자열 3개를 한번에 비교하는 방법을 사용해야 한다.

2차원 배열로 하는 LCS 연산을 이해하고 있다면, 3차원으로 확장하는 것 자체는 크게 어렵지 않았다.

3차원은 직관적이지 않고 머리에 한번에 들어오지 않아 어려울 수 있지만, 결국 문자열 3개를 비교하는 것이 목적이기 때문에 무엇을 위해 3차원 배열을 사용하는지를 생각하면 쉽다.

모든 과정이 어떤 목적을 가지고 있는지를 정확하게 알고 있어야 확장이 쉬울 것이다.

코드

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

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

int board[101][101][101];

string LCS3(string x, string y, string z){
	x = ' ' + x;
	y = ' ' + y;
	z = ' ' + z;
	
	for (int i = 1; i < x.length(); i++){ //LCS Board
		for (int j = 1; j < y.length(); j++){
			for (int k = 1; k < z.length(); k++){
				if (x[i] == y[j] && y[j] == z[k])
					board[i][j][k] = board[i-1][j-1][k-1] + 1;
				else
					board[i][j][k] = max(board[i-1][j][k], max(board[i][j-1][k], board[i][j][k-1]));
			}
		}
	}
	
	debug << x << ' ' << y << ' ' << z << endl;
	for (int i = 1; i < x.length(); i++){ //LCS Board
		for (int j = 1; j < y.length(); j++){
			for (int k = 1; k < z.length(); k++){
				debug << board[i][j][k];
			} debug << endl;
		} debug << endl << endl;
	}
	
	// find LCS
	int px = x.length()-1;
	int py = y.length()-1;
	int pz = z.length()-1;
	
	string result;
	while (board[px][py][pz] != 0){
		if (x[px] == y[py] && y[py] == z[pz]){ // downgrade
			result = x[px] + result;
			px--; py--; pz--;
		}
		else{
			int target = max(board[px-1][py][pz], max(board[px][py-1][pz], board[px][py][pz-1]));
			if (target == board[px-1][py][pz]) px--; 
			else if (target == board[px][py-1][pz]) py--;
			else pz--;
		}
	}
	
	return result;
}

int main(){
	string a, b, c;
	cin >> a >> b >> c;
	
	string r = LCS3(a, b, c);
	cout << r.length() << endl;
	debug << r;
}