10330번 - 비트 문자열 재배열하기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 196 | 123 | 107 | 67.296% |
문제
비트 문자열은 0, 1로만 이루어진 문자열이다. 여러분은 비트 문자열을 하나 받아서 특정한 문자열로 바꾸어야 한다. 이때, 여러분이 유일하게 할 수 있는 연산은 인접한 두 비트를 바꾸는 것이다.
초기 문자열의 상태는 그냥 비트의 순열로 주어진다. 하지만 바꾸고자 하는 문자열은 '연속 코드'의 형태로 주어진다. 연속 코드란, 문자열에 나타나는 연속된 0 또는 1의 개수를 차례대로 늘어놓은 순열이다. 예를 들어, "011100"의 연속 코드는 "1 3 2"가 된다. 이때, 여러분도 눈치챘겠지만 연속 코드가 같은 문자열은 0으로 시작하는 것 하나, 그리고 1로 시작하는 것 하나로 항상 두 개씩 있다.
초기 문자열에서 나중 문자열로 문자열을 바꾸는데 필요한 최소한의 연산의 수를 계산하여라.
입력
입력의 첫 줄에는 두 정수 N (1 ≤ N ≤ 15)과 M (1 ≤ M ≤ N)이 주어진다. 둘째 줄에는 N개의 비트가 공백을 사이에 두고 주어진다. 이는 초기 문자열을 의미한다. 셋째 줄에는 바꿔야 하는 문자열의 연속 코드가 M개의 정수로 차례대로 주어진다.
바꿔야 하는 연속 코드의 각 숫자는 항상 1보다 크거나 같고, 그 코드를 모두 더하면 N이 되고, 주어진 비트 문자열이 항상 연속 코드가 나타내는 비트 문자열로 변환될 수 있음이 보장된다.
출력
필요한 최소한의 연산 수를 출력한다.
예제 입력 1
6 3 1 0 0 1 0 1 1 3 2
예제 출력 1
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이 답이다.
출처
ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2014 in Tokyo A번
- 문제의 오타를 찾은 사람: baemin0103, YunGoon
- 문제를 번역한 사람: junie
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호