Brickor
시간 제한1초메모리 제한1024 MB
흑백 조각이 놓인 짧은 줄에서 인접한 두 조각을 떼어 뒤집은 뒤 줄의 맨 앞이나 맨 뒤에 붙이는 이동을 반복해, 모든 조각을 흰 면으로 만드는 최소 이동 횟수를 구한다.
문제
Karin은 한쪽이 검은색이고 다른 쪽이 흰색인 오셀로 돌로 하는 혼자 하는 놀이를 만들었다. 그녀는 돌을 한 줄로 늘어놓는데, 각 돌은 검은색이거나 흰색이다. 목표는 모든 돌이 흰색 면이 위로 오게 만드는 것이다.
"이동"이란 줄의 어딘가에서 인접한 돌 한 쌍을 "꺼내서" 뒤집고(흰색은 검은색이 되고 검은색은 흰색이 된다), 쌍의 순서는 바꾸지 않은 채 줄의 맨 앞이나 맨 뒤에 다시 놓는 것이다.
돌의 처음 줄이 주어졌을 때, 모든 돌을 흰색으로 만들기 위해 필요한 최소 이동 횟수를 출력하는 프로그램을 작성하시오.
입력
입력은 문자 S와 V로만 이루어진 문자열이다. 문자열의 길이는 3에서 15 사이이다.
출력
모든 돌을 흰색으로 만들기 위해 필요한 최소 이동 횟수를 나타내는 하나의 정수를 출력한다. 주어지는 테스트 데이터에서는 목표를 달성하는 것이 항상 가능하다.
힌트
예제 2의 가능한 이동 순서