중첩 뒤집기 수열
시간 제한2초메모리 제한128 MB
두 이진 문자열이 주어질 때, 구간이 점점 좁아지도록 중첩된 부분문자열 뒤집기 연산만으로 하나를 다른 하나로 바꾸는 최소 연산 횟수를 구하는 문제입니다.
문제
길이가 같은 두 이진 문자열 A와 B가 있다. 한 번의 연산 r(i, j)는 현재 문자열에서 0번부터 센 i번째 문자부터 j번째 문자까지의 부분 문자열을 뒤집는다.
여러 연산을 사용할 때는 순서가 제한된다. 연산들이 r(i_1, j_1), r(i_2, j_2), ..., r(i_m, j_m) 순서로 수행된다면 다음 조건을 모두 만족해야 한다.
- i_1 <= i_2 <= ... <= i_m
- j_1 >= j_2 >= ... >= j_m
즉, 뒤에 수행하는 연산의 구간은 앞에서 수행한 구간의 안쪽에 있어야 한다. 문자열 A를 B로 바꾸는 데 필요한 최소 연산 횟수를 구하시오.
입력
첫째 줄에 이진 문자열 A가 주어진다. 둘째 줄에 이진 문자열 B가 주어진다.
두 문자열의 길이는 같고 50 이하이다. 두 문자열은 문자 0과 1로만 이루어져 있다.
출력
문자열 A를 B로 바꾸는 데 필요한 최소 연산 횟수를 출력한다. 조건을 만족하는 연산 수열로 바꿀 수 없으면 -1을 출력한다.