[마이다스챌린지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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#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; }