1958번: LCS 3

메모리

시간

5924 KB

4 ms

Code

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main(int argc, char const *argv[])
{
	int result[101][101][101] = {0,};
	char one[101];
	char two[101];
	char three[101];

	scanf("%s", one);
	scanf("%s", two);
	scanf("%s", three);
	
	int	i_len = strlen(one);
	int	j_len = strlen(two);
	int	z_len = strlen(three);
	int comp = 0;

	
	for (int i = 1; i <= i_len; i++)
	{
		for (int j = 1; j <= j_len; j++)
		{
			for (int z = 1; z <= z_len; z++)
			{
				if (one[i - 1] == two[j - 1] && one[i - 1] == three[z - 1])
					result[i][j][z] = result[i - 1][j - 1][z - 1] + 1;
				else
				{
					comp = max(result[i][j][z - 1], result[i - 1][j][z]);
					result[i][j][z] = max(result[i][j - 1][z], comp);
				}
			}
		} 
	}
	cout << result[i_len][j_len][z_len] << endl;

	return 0;
}

문제 풀이

LCS 1 에서 풀었던 2차원 배열을 3차원으로 변경하여 풀이하였다.

3중 for 문과 max 값 비교를 수정 해주었다.