카드 손패 정리

시간 제한1초메모리 제한512 MB

요약

서로 다른 카드 최대 52장이 주어질 때, 각 무늬가 한 덩어리를 이루고 그 안의 순위가 오름차순이나 내림차순이 되도록 카드를 뽑아 다시 끼워 넣는 최소 횟수를 구한다.

난이도: 보통10점 중 7점
유형: 정렬, 완전 탐색, 동적 계획법
정답자: 아직 제출이 없습니다

문제

카드 게임 Plump에서는 받은 카드를 무늬와 숫자에 따라 정리하고 시작하는 편이 좋다. 손패가 정리된 상태란 같은 무늬의 카드가 모두 연속된 한 덩어리를 이루고, 각 덩어리 안에서 숫자가 오름차순이거나 내림차순인 상태를 말한다. 무늬 덩어리끼리의 순서는 상관없고 덩어리마다 방향을 따로 정할 수 있다. 즉 어떤 무늬는 오름차순이고 다른 무늬는 내림차순이어도 된다.

한 번의 이동은 카드 한 장을 손패에서 빼내어 다른 위치에 다시 꽂는 것이다. 맨 앞, 맨 뒤, 인접한 두 카드 사이 중 어디에나 꽂을 수 있고 나머지 카드의 상대 순서는 그대로 남는다. 주어진 손패를 정리하는 데 필요한 이동 횟수의 최솟값을 구하라.

입력

첫째 줄에 손패의 카드 개수 $n$ ( $1 \le n \le 52$ )이 주어진다. 둘째 줄에 서로 다른 카드 $n$ 장이 공백으로 구분되어 주어진다. 각 카드는 두 글자다. 첫 글자는 숫자를 나타내며 2부터 9까지의 한 자리 수 또는 T, J, Q, K, A 중 하나다. T, J, Q, K, A는 각각 10, 잭, 퀸, 킹, 에이스를 뜻하고 여기 나열한 순서가 숫자의 오름차순이다. 둘째 글자는 무늬를 나타내며 스페이드 s, 하트 h, 다이아몬드 d, 클럽 c 중 하나다.

출력

손패를 정리하는 데 필요한 최소 이동 횟수를 출력한다.

예제3

예제 1
입력
```
4
2h Th 8c Qh
```
예상 출력
```
1
```
예제 2
입력
```
7
9d As 2s Qd 2c Jd 8h
```
예상 출력
```
2
```
예제 3
입력
```
4
2h 3h 9c 8c
```
예상 출력
```
0
```