Problems
이진 문자열(0과 1로 구성된 문자열)이 주어졌을 때, 그 중 연속되는 문자열을 뒤집어서 원하는 문자열로 만드는 프로그램을 작성하라.
예를 들어 처음에 주어진 문자열이 1100 이고, 최종적으로 만들 문자열이 0110 이라고 할 경우에 첫 번째 문자부터 세 번째 문자까지를 뒤집게 되면 원하는 문자열이 생성된다. 하지만 뒤집기에는 제약 조건이 있다. i번째 문자부터 j번째 문자까지 뒤집었을 때를 (i, j)라고 하자.
그 다음 첫 번째 뒤집기를 했을 경우 (i1, j1), 두 번째는 (i2, j2), ... , 최종적으로 n번째를 뒤집었을 경우 (in, jn)라고 하자.
그러면 다음 조건을 만족해야 한다. i1 ≤ i2 ≤ ... ≤ in 이고 j1 ≥ j2 ≥ ... ≥ jn 이어야 한다.
Input
입력은 여러 개의 테스트 케이스로 구성된다.
테스트 케이스는 2개의 문자열로 구성 되며 첫 번째는 주어진 이진 문자열, 그리고 두 번째는 최종적으로 만들고자 하는 이진 문자열이다.
두개의 문자열의 개수는 같으며, 최대 50글자 이하의 문자열이 주어진다. 테스트 케이스에 END END가 들어올 경우 프로그램을 종료한다.
Output
각 테스트 케이스에 대해 원하는 문자열을 만들기 위해 필요한 최소한의 뒤집기 횟수를 한 줄에 출력한다. 만약 불가능할 경우 -1을 출력한다.
Example
1100 0110
111000 101010
0 1
10101 10101
1110010b00 001100110011
END END
1
2
-1
0
4
You must sign in to write code.