[마이다스챌린지2017예선] 트럼프카드 문제 (TrumpCard)

트럼프카드 문제 (TrumpCard)

트럼프 카드가 얼마나 잘 섞였는지 판단하는 알고리즘을 개발하려고 합니다. 섞기 전의 카드 배열과 섞은 후의 카드 배열의 순서가 같은 부분배열들 중 섞기 전과 섞은 후에 공통으로 나타나며 길이가 가장 긴 것을 구해서 그 길이를 M 이라고 합니다. 그리고 M 값이 작을수록 카드가 잘 섞인 것으로 간주하기로 합니다. 이 때 부분배열은 연속되지 않아도 됩니다. 트럼프 카드는 모양이 없고 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A 로만 이루어진 것을 사용합니다.

예를 들어

[ 2, 3, 4 ] 와 순서가 같은 부분배열은 [ 2 ], [ 3 ], [ 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ], [ 2, 3, 4 ] 입니다. ( 연속되지 않아도 순서만 같으면 되기 때문에 [ 2, 4 ] 도 가능 )

카드 배열이 다음과 같다면

섞기 전 = [ 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A ]

섞은 후 = [ 3, J, 2, Q, 10, K, 4, 9, 5, 8, 6, A, 7 ]

두 카드 배열의 순서가 같은 부분배열 중 공통으로 나타나며 길이가 가장 긴 것은 [ 3, 4, 5, 6, 7 ], [ 3, J, Q, K, A ], … 등이 있으며 M 값은 5 가 됩니다.

주어진 카드 배열로 M 값을 구하는 프로그램을 작성하십시오.

입력

입력은 표준 입력(stdin)으로 주어지며

첫째 줄에 섞기 전 카드 배열이 주어집니다.

둘째 줄에 섞은 후 카드 배열이 주어집니다.

각 카드는 다음 문자열로 표현하며 카드와 카드는 공백으로 구분됩니다.

2 3 4 5 6 7 8 9 10 J Q K A

출력

출력은 표준 출력(stdout)으로 이루어집니다.

첫째 줄에 M 값을 출력합니다.

입력예)

2 3 4 5 6 7 8 9 10 J Q K A

3 J 2 Q 10 K 4 9 5 8 6 A 7

출력예)

5

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main()
{
	string Card1[13];
	string Card2[13];
	for (int i = 0; i < 13; i++)
	{
		string n;
		cin >> n;
		Card1[i] = n;
	}

	for (int i = 0; i < 13; i++)
	{
		string c;
		cin >> c;
		Card2[i] = c;
	}

	int Card_pos[13] = { 0 };
	int memo[13] = { 0 };
	for (int i = 0; i < 13; i++)
	{
		for (int j = 0;j < 13; j++)
		{
			if (Card1[i] == Card2[j])
			{
				Card_pos[j] = i;
				break;
			}
		}
	}

	for (int i = 12; i >= 0; i--)
	{
		for (int j = i; j < 13; j++)
		{
			if (Card_pos[i] <= Card_pos[j])
				memo[i] = max(memo[i], memo[j] + 1);
		}
	}

	cout << *max_element(memo, memo + 13);
	return 0;
}