Informatica Online Judge

  크리스 마틴 [1751 / 06D7]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 7   Total Tried : 25


The Champion of this Problem (C++) : ajou709 - 0ms / 281byte
My Best Submission (C++) : N/A

[2016 나는코더다 송년 대회 (Polish Collegiate Programming Contest 2012)]

Background

미친 과학자 창호는 어젯 밤 구재현을 납치해서, 구재현의 DNA를 추출했다. 인간의 DNA의 길이는 $n$이며, $A$, $C$, $G$, $T$ 4개의 염색체로 구성되어 있다.

창호는 매일 자신을 놀리던 구재현을 좋아하지 않고, 대신 잘 생긴 콜드플레이의 크리스 마틴을 더 좋아한다. 이러한 경험을 토대로 창호는 이론을 하나 만들었다. 창호의 이론에 따르면, 구재현의 DNA와의 유사도가 최소인 DNA가 크리스 마틴의 DNA이다.

두 DNA의 유사도는, 두 DNA 간의 최장 공통 부분 수열(LCS)의 길이를 뜻한다. 어떠한 DNA의 부분 수열은, 그 DNA에서 0개 이상의 원소를 제거해서 만들 수 있는 또 다른 DNA 수열을 뜻한다. 두 DNA $A$, $B$의 최장 공통 부분 수열은, $A$와 $B$의 부분 수열이면서, 길이가 최대인 수열들을 뜻한다.

사실 잘 몰랐겠지만, 여러분도 지금 창호에게 납치되어 있다. 크리스 마틴의 DNA를 구하지 못하면 여러분에게 무슨 일이 일어날 지 모른다. 빨리 크리스 마틴의 DNA를 구하자. 원래는 DNA를 찾아야 했지만, 이상한 아이인 창호는 변덕이 나서, 최소 유사도만 찾아도 Accepted를 줄 예정이다.

Input

첫번째 줄에 인간 DNA의 길이 $n$이 주어진다. ($1 <=n <= 10,000$) 이 주어진다.

이후 길이 $n$의 DNA 문자열이 주어진다. 문자열의 모든 문자는 $A$, $C$, $G$, $T$ 넷 중 하나다.

Output

최소 유사도를 출력한다.

IO Example

입력
4
GACT

출력
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]