볼 모으기(balls) > 문제은행



실력키우기 여러가지

3427 : 볼 모으기(balls)

제한시간: 1000 ms    메모리제한: 1024 MB
해결횟수: 48 회    시도횟수: 162 회   



빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을때, 

볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 

 

볼을 옮기는 규칙은 다음과 같다.

 

1. 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 

   즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.

   유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.

2. 옮길 수 있는 볼의 색깔은 한 가지이다.

   즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다.

   유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.

 

예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후,

<그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은색끼리 모을 수 있다.​

 

592d7a7e0c8d86d1da5cb1fdc052ff77_1563701
 


반면에 파란색 볼을 선택하여 <그림 4>에서 보인 것처럼 옮기면

(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.​

 

592d7a7e0c8d86d1da5cb1fdc052ff77_1563701
 

일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 

같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.​

 




표준 입력으로 다음 정보가 주어진다. 
첫 번째 줄에는 볼의 총 개수 N이 주어진다.(1 ≤ N ≤ 500,000) 
다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백
없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주어질 수도 있으며, 이 경우 답은 0이 된다.



표준 출력으로 최소 이동횟수를 출력한다.

[부분문제의 제약 조건]
* 부분문제 1: 전체 점수 100점 중 15점에 해당하며 N ≤ 10. 
* 부분문제 2: 전체 점수 100점 중 22점에 해당하며 N ≤ 1,000.
* 부분문제 3: 전체 점수 100점 중 14점에 해당하며 N ≤ 500,000 이고, 
              처음 상태에서 모든 파란 공은 연속해서 존재한다. 
* 부분문제 4: 전체 점수 100점 중 49점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.


9
RBBBRBRRR
2


8
BBRBBBBR
1



데이타 만든사람 : donghyien



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