연산 최적화
시간 제한2초메모리 제한256 MB
빈 문자열에 0 또는 1을 붙이거나 현재 문자열을 복사해 붙이는 연산을 순서대로 모은 F를 두 번 적용해 주어진 이진 문자열 S를 만들 때, 가장 짧은 F의 길이를 구한다.
문제
퍼즐 게임을 좋아하는 현욱이 오늘도 재미있는 퍼즐을 하나 찾아냈다. 플레이어는 빈 문자열 하나를 들고 시작하고, 문자열에 다음 세 가지 연산을 쓸 수 있다.
- A: 현재 문자열의 맨 뒤에 0을 붙인다.
- B: 현재 문자열의 맨 뒤에 1을 붙인다.
- C: 현재 문자열과 똑같은 문자열을 현재 문자열의 맨 뒤에 덧붙인다.
플레이어는 이 연산을 순서대로 이어 붙여 새 연산 를 만들 수 있다. 는 사용한 연산을 순서대로 나열해 적는다. 예를 들어 는 주어진 문자열의 맨 뒤에 10을 덧붙이는 연산이다.
퍼즐에는 목표 문자열 가 주어진다. 빈 문자열에 를 두 번 적용한 결과가 와 같아야 한다. 즉 빈 문자열에 를 적용해 얻은 문자열에 를 한 번 더 적용하면 가 나와야 한다.
예를 들어 가 100100이면 가 조건을 만족한다. 빈 문자열에 를 적용하면 100이 되고, 100에 를 다시 적용하면 100100이 된다.
의 길이, 즉 에 쓴 연산의 개수가 적을수록 점수가 높다. 현욱을 도와 조건을 만족하는 가장 짧은 의 길이를 구하자.
입력
첫째 줄에 목표 문자열 의 길이 이 주어진다(). 둘째 줄에 목표 문자열 가 주어진다. 는 0과 1로만 이루어져 있다.
출력
조건을 만족하는 가장 짧은 의 길이를 출력한다. 그러한 가 없으면 -1을 출력한다.