AB-단어

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

요약

최대 1000개의 nice ab-word(균형 잡힌 괄호 문자열)가 주어질 때, 재귀적으로 정의된 유사 관계에서 서로 유사하지 않은 단어들의 최대 부분집합의 크기를 구한다.

난이도: 어려움10점 중 9점
유형: 트리, 해시맵, 재귀, 정렬
정답자: 아직 제출이 없습니다

문제

소문자 a와 b로 이루어진 모든 수열(빈 수열 포함)을 ab-단어라고 부른다. $X = [x_1, \dots, x_n]$ 이 ab-단어이고 $1 \le i \le j \le n$ 이면, $X[i..j]$ 는 $x_i, \dots, x_j$ 로 이루어진 부분 단어를 뜻한다.

ab-단어 $X = [x_1, \dots, x_n]$ 에서 a의 개수와 b의 개수가 서로 같고, 모든 $i = 1, \dots, n$ 에 대해 접두사 $X[1..i]$ 의 a 개수가 b 개수 이상이면, 이 단어를 좋은(nice) 단어라고 한다.

좋은 ab-단어 사이의 유사성(similarity)은 다음과 같이 귀납적으로 정의한다.

빈 ab-단어 둘은 서로 유사하다.
비어 있지 않은 두 좋은 ab-단어 $X = [x_1, \dots, x_n]$ $X = [x_{1}, \dots, x_{n}]$ 와 $Y = [y_1, \dots, y_m]$ $Y = [y_{1}, \dots, y_{m}]$ 는 길이가 같고( $n = m$ $n = m$ ) 아래 조건 중 하나 이상을 만족하면 서로 유사하다.
- $x_1 = y_1$ , $x_n = y_n$ 이고, $X[2..n-1]$ 와 $Y[2..n-1]$ 가 모두 좋은 단어이면서 서로 유사하다. 또는
- 어떤 $i$ $i$ ( $1 \le i \le n$ $1 \leq i \leq n$ )가 존재하여 $X[1..i]$ $X [1.. i]$ 와 $X[i+1..n]$ $X [i + 1.. n]$ 가 모두 좋은 단어이고, 다음 중 하나가 성립한다.
  - $Y[1..i]$ 와 $Y[i+1..n]$ 가 모두 좋은 단어이며, $X[1..i]$ 는 $Y[1..i]$ 와 유사하고 $X[i+1..n]$ 는 $Y[i+1..n]$ 와 유사하다. 또는
  - $Y[1..n-i]$ 와 $Y[n-i+1..n]$ 가 모두 좋은 단어이며, $X[1..i]$ 는 $Y[n-i+1..n]$ 와 유사하고 $X[i+1..n]$ 는 $Y[1..n-i]$ 와 유사하다.

비어 있지 않은 좋은 ab-단어들의 집합 $S$ 의 다양성 수준(level of diversity)은, 고른 어떤 두 단어도 서로 유사하지 않도록 $S$ 에서 고를 수 있는 단어의 최대 개수이다.

표준 입력에서 집합 $S$ 를 읽어 $S$ 의 다양성 수준을 계산하고, 그 결과를 표준 출력에 출력하는 프로그램을 작성하여라.

입력

첫째 줄에 집합 $S$ 의 원소 개수 $n$ 이 주어진다 ( $1 \le n \le 1000$ ). 다음 $n$ 개의 줄에는 각각 $S$ 의 원소, 즉 좋은 ab-단어가 한 줄에 하나씩 주어진다. 각 단어는 줄의 맨 앞에서 시작하며 글자 사이에 공백은 없다. 모든 ab-단어의 길이는 $1$ 이상 $200$ 이하이다.

출력

$S$ 의 다양성 수준을 나타내는 정수 하나를 출력한다.

예제1

예제 1
입력
```
3
aabaabbbab
abababaabb
abaaabbabb
```
예상 출력
```
2
```