여러분은 유리알이 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이다.

목걸이(The necklace of beads) timer 1초 memory 64MB

목걸이(The necklace of beads) 1초 64MB