소들의 안무

소들이 댄스 팀을 결성했고, 농부 존이 안무가를 맡았다! 팀의 최신 최고 안무에는 \(N\)마리의 소(\(2 \le N \le 10^6\))가 한 줄로 서 있다. 안무의 각 동작은 최대 \(K\)칸 떨어진(\(1 \le K < N\)) 두 소가 우아하게 점프하여 서로의 위치에 착지하는 것으로 이루어진다.

줄에는 건지(Guernsey)와 홀스타인(Holstein)이라는 두 종류의 소가 있다. 그래서 농부 존은 안무를 길이 \(N\)의 이진 문자열들의 수열로 기록했다. \(0\)은 건지, \(1\)은 홀스타인을 나타내며, 전체 문자열은 소들이 줄에 어떻게 배치되어 있는지를 나타낸다.

안타깝게도 (라이벌 팀의 안무를 맡은) 농부 은조이가 안무를 방해하여 첫 번째와 마지막 이진 문자열을 제외한 모든 것을 지워 버렸다! 큰 대회가 코앞으로 다가온 만큼, 농부 존은 지체 없이 안무를 복원해야 한다.

이 두 이진 문자열이 주어졌을 때, 안무에 필요한 최소 동작 수를 찾도록 농부 존을 도와주자!

문제 제공: Benjamin Qi

배점

• 입력 4-5: \(K=1\)
• 입력 6-7: 두 문자열 모두 \(1\)이 최대 \(8\)개이다.
• 입력 8-15: \(N\le 5000\)
• 입력 16-23: 추가 제약 없음.

문제 제공: Benjamin Qi

첫째 줄에 \(N\)과 \(K\)가 주어진다.

둘째 줄에 첫 번째 이진 문자열이 주어진다.

셋째 줄에 마지막 이진 문자열이 주어진다.

두 이진 문자열에 포함된 \(1\)의 개수가 같음이 보장된다.

안무에 필요한 최소 동작 수를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > US Open > Gold