진희는 N명으로 이루어진 아이돌 그룹의 안무가다. 춤의 각 동작은 서로 최대 K자리 떨어져 있는 두 명의 멤버가 서로의 위치를 교환하는 것이다.

해당 아이돌 그룹은 혼성 그룹으로 남자 멤버와 여자 멤버가 존재한다. 따라서 진희는 춤을 길이가 N인 이진 문자열로 기록했으며, 여기서 0은 여성 멤버를, 1은 남성 멤버를 나타내며 전체 문자열은 아이돌 멤버들이 줄을 서서 배열된 방식을 나타낸다.

불행하게도 경쟁사 안무가인 혁준이가 진희를 방해하기 위해 첫 번째와 마지막 이진 문자열을 제외한 모든 것을 지웠다! 큰 공연이 곧 있을 예정이기에 진희는 춤을 재구성하는 데 시간을 낭비할 수 없다.

첫 번째와 마지막 이진 문자열이 주어졌을 때, 진희를 도와 춤을 재구성하기 위해 필요한 최소 동작 수를 구하는 프로그램을 작성하시오.

아이돌 안무가 timer 2s memory 1024MB

아이돌 안무가 2s 1024MB