IOI 1993 1- 목걸이(The necklace of beads) > 문제은행 : 정보올림피아드&알고리즘




1114 : 목걸이(The necklace of beads)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
28 회   
시도횟수
70 회   

문제

여러분은 유리알이 n개 있는(n≤350) 목걸이를 갖고 있다. 

목걸이에는 빨간색, 파란색 또는 흰색 유리알이 아무렇게나 배열돼 있다. n=29인 경우의 두 가지 예를 다음에 들어보았다.

 

 


 

 

그림 1에 있는 목걸이는 b와 r로 되어 있는 문자열로 표현할 수 있다. b는 푸른 알, r은 붉은 알을 뜻한다. 

이를 표현하면 brbrrrbbbrrrrrbrrbbrbbbbrrrrb와 같이 될 것이다. 

단, 그림에 있는 1번 위치부터 시작하여 2번이 있는 방향, 즉 시계 방향으로 알을 나열한 것이다.

 

이 목걸이의 한 부분을 끊어서 한 줄로 늘어놓는다고 생각해 보자. 그래서 첫 줄에서부터 같은 색이 계속되는 유리알들을 모은다. 

그리고 끝줄에서부터 같은 색이 계속되는 유리알들을 모은다. (첫줄의 알 색과 끝줄의 알 색은 다를 수 있다.)

 

목걸이의 어디를 끊으면 알을 가장 많이 모을 수 있는지 계산하는 프로그램을 작성하라. 

예를 들어 그림 1의 목걸이는 9째 알과 10째 알 사이, 혹은 24와 25 사이를 끊었을 때 최대치인 8개의 알을 모을 수 있다. 원리는 다음과 같다.

 

brbrrrbbb/rrrrrbrrbbrbbbbrrrrb → (rrrrr)brrbbrbbbbrrrrbbrbrrr(bbb)
brbrrrbbbrrrrrbrrbbrbbbb/rrrrb → (rrrr)bbrbrrrbbbrrrrrbrrbbr(bbbb)

 

그런데 어떤 목걸이에는 그림 2처럼 흰색 알이 섞여 있다. 

알을 모을 때, 흰색 알은 알을 더 많이 모으기 위해서라면 어떤 색으로든 칠할 수 있다. 흰색 알을 뜻하는 문자열은 w이다.

 


입력형식

입력의 첫 번째 줄에는 목걸이의 길이 n이 입력된다. 그리고 길이 n의 문자열이 들어오며 이는 목걸이를 뜻한다.


출력형식

끊어서 가장 많이 모을 수 있는 알의 개수를 출력한다.


입력 예

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

출력 예

11

출처

IOI 1993 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