[C++] 비밀 메뉴2

[문제]

https://softeer.ai/practice/info.do?idx=1&eid=633 

Softeer

[문제 풀이]

조건에서 N과 M이 3000이 안되니 n^2 으로도 시간제한 안에 충분히 풀 수 있었던 문제였기에 LCS 알고리즘을 응용해서 풀었다.

N의 배열과 M의 배열을 이중으로 교차시키고 제일 많이 나오는 연속된 숫자를 답으로 체크하였다.

* LCS 알고리즘에 관한 설명은 이쪽에 있다. https://yoon-1212.tistory.com/108

[코드]

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{

	int n,m,k;
	cin>>n>>m>>k;
	vector<int> firstKio(n,0);
	vector<int> secondKio(m,0);
	for(int i = 0;i<n;i++){
		cin>>firstKio[i];
	}
	for(int i = 0;i<m;i++){
		cin>>secondKio[i];
	}

	vector<vector<int> > menu(n + 1,vector<int>(m + 1,0));

	int answer = 0;

	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			if(firstKio[i - 1] == secondKio[j - 1]){
				menu[i][j] = menu[i-1][j-1] + 1;
			}
			answer = max(answer, menu[i][j]);
		}
	}

	cout<<answer<<endl;

	return 0;
}