이 문제는 3-SAT에서 다항 시간 환원이 가능한 NP-하드 문제인 데다가, 답을 기하급수적으로 키울 수 있습니다. (답의 상한은 doju님이 지적하셨습니다.)

NP-하드라는 점은 간단하게 해결할 수 있습니다. 원래는 NP-하드가 아닌데 조건이 하나 빠진 것이기 때문입니다.

1. 4번 특징의 끝에 "처음 나오는 1의 위치는 모두 다르다."를 추가해 주세요.
2. 입력 설명의 "빈칸을 사이에 두고 주어진다." 뒤에 "단위 이동은 처음 나오는 1의 위치가 증가하는 순서대로 주어진다."를 추가해 주세요.

위 조건은 모두 assert문으로 확인하였습니다.

하지만 풀이를 수정하지 않으면서 답의 상한 조건을 해결할 방법은 찾지 못했고, 아마 없을 것이라고 생각됩니다. 현재 "도달 가능한 입력"의 답이 int 범위에 있음은 assert문으로 확인하였으나, 그렇게 조건을 걸어도 "도달 불가능한 입력"에서는 아무것도 보장할 수 없습니다.