COCI 2012/2013 - 번역 : functionx <br>2013.02.23 모의테스트2- 점 잇기(ESEJ) > 문제은행 : 정보올림피아드&알고리즘




1625 : 점 잇기(ESEJ)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
21 회   
시도횟수
60 회   

문제

N개의 수평선이 있다. 각 수평선 위에는 점들이 있어서 청록색 또는 파란색으로 색칠되어 있다. 이 때, 다음 네 조건을 만족하게 점들을 연결할 수 있는 수평선의 수를 구하는 프로그램을 작성하여라.




1) 각 점을 지나는 선은 정확히 1개이다.

2) 연결된 두 점의 색은 같다.

3) 모든 연결선들이 수평선 위에 있다.

4) 임의의 두 연결선들도 교차하지 않는다.


입력형식

첫 번째 줄에는 N이 주어진다. (1 ≤ N ≤ 100) K+1번째 줄 (1 ≤ K ≤ N)에는 K번째 수평선에 있는 점들의 색깔이 순서대로 주어진다. 이 때, 청록색은 문자 A로, 파란색은 문자 B로 주어진다. 한 행의 문자열의 길이는 2이상 100,000 이하이다. 또한 모든 문자열들의 길이의 합은 1000,000을 초과하지 않는다.

출력형식

주어진 네 조건을 만족하게 점들을 연결할 수 있는 수평선의 수를 출력한다.

입력 예

3 
ABAB 
AABB 
ABBA

출력 예

2

입력 예

3 
AAA 
AA 
AB

출력 예

1

입력 예

1 
ABBABB

출력 예

1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP