시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 87 54 42 61.765%

문제

비트 문자열은 0, 1로만 이루어진 문자열이다. 여러분은 비트 문자열을 하나 받아서 특정한 문자열로 바꾸어야 한다. 이 때, 여러분이 유일하게 할 수 있는 연산은 인접한 두 비트를 바꾸는 것이다.

초기 문자열의 상태는 그냥 비트의 순열로 주어진다. 하지만 바꾸고자 하는 문자열은 '연속 코드'의 형태로 주어진다. 연속 코드란, 문자열에 나타나는 연속된 0 또는 1의 갯수를 차례대로 늘어놓은 순열이다. 예를 들어, "011100"의 연속 코드는 "1 3 2"가 된다. 이 때, 여러분도 눈치챘겠지만 연속 코드가 같은 문자열은 0으로 시작하는 것 하나, 그리고 1로 시작하는 것 하나로 항상 두 개씩 있다.

초기 문자열에서 나중 문자열로 문자열을 바꾸는데 필요한 최소한의 연산의 수를 계산하여라.

입력

입력의 첫 줄에는 두 정수 N (1 ≤ N ≤ 15)과 M (1 ≤ M ≤ N)이 주어진다. 둘째 줄에는 N개의 비트가 공백을 사이에 두고 주어진다. 이는 초기 문자열을 의미한다. 셋째 줄에는 바꿔야 하는 문자열의 연속 코드가 M개의 정수로 차례대로 주어진다.

바꿔야 하는 연속 코드의 각 숫자는 항상 1보다 크고, 그 코드를 모두 더하면 N이 되고, 주어진 비트 문자열이 항상 연속 코드가 나타내는 비트 문자열로 변환될 수 있음이 보장된다.

출력

필요한 최소한의 연산 수를 출력한다.

예제 입력

6 3
1 0 0 1 0 1
1 3 2

예제 출력

1

예제 입력 2

7 2
1 1 1 0 0 0 0
4 3

예제 출력 2

12

예제 입력 3

15 14
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 2

예제 출력 3

7

예제 입력 4

1 1
0
1

예제 출력 4

0

힌트

예제 입력 1에서 비트 문자열 "100101"은 연속 코드가 "1 3 2"인 비트 문자열로 재배열되어야 한다. 즉, "100011"이나 "011100" 둘 중 한 가지 문자열로 재배열되어야 하는 것이다. "011100"으로 문자열을 바꾸기 위해서는 4번의 연산이 필요하지만 "100011"로 바꾸기 위해서는 1번의 연산이면 충분하다. 따라서 이 경우에는 1이 답이다.

출처

ACM-ICPC > Regionals > Asia > Japan > Asia Regional Contest 2014 in Tokyo A번

  • 문제의 오타를 찾은 사람: baemin0103
  • 문제를 번역한 사람: junis3