목걸이 > 문제은행

본문 바로가기


실전대비 Level2

1114 : 목걸이

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 109 회    시도횟수: 458 회   



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

 

e3050b66a1b29a01767400d7560a4131_1449730
 

 

그림 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의 문자열이 들어오며 이는 목걸이를 뜻한다.



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


[Copy]
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
[Copy]
11


출처 : IOI93


IOI93 1_The necklace of beads.

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.