디자이너 ‘예처르킴’은 요즘 탭 댄스를 배운다. 그는 아직 초보자라 고급 기술은 못하고 그저 왼발, 오른발 꾸준히 연습하고 있다. 그가 탭 댄스를 배우면서 같은 발을 두 번 연속 치는 동작은 별로 아름답지 못 하다는 것을 느꼈다. 그는 간단한 안무 동작들에 아름다움의 정도를 매겼다. ‘예처르킴’이 매긴 안무의 아름다움의 정도란, 안무 동작들 중에서 연속으로 같은 발을 치지 않는 최대 부분 안무의 길이다.
예를 들어, 안무가 ‘LLRLRLRR’ 이라면, 2번째 동작부터 7번째 동작까지 같은 발을 연속으로 치지 않으므로 저 안무의 아름다움의 정도는 6이다. ‘예처르킴’은 조금씩 안무를 바꿔가고 있는 그는 매순간 안무의 아름다운 정도가 궁금했다. 당신은 그를 도와 매 순간 안무의 아름다운 정도를 구하자.
처음 안무의 길이는 N이고, 그는 안무를 M번 수정한다. 그가 안무를 한번 수정할 때는 어떤 한 동작을 뒤집는다. (L은 R로 R은 L로). 그가 계획한 맨 처음 안무는 모두 왼발을 치는 것이다. (안무 ‘LLL…LLL’).
입력 6 2 2 4 출력 3 5 입력 6 5 4 1 1 2 6 출력 3 3 3 5 6
출처:koi4u 2011 2차 모의고사 1번