15507번 - 연산 최적화

퍼즐 게임을 좋아하는 현욱은 오늘도 흥미로운 퍼즐 하나를 찾아냈다. 이 퍼즐 게임에서 플레이어는 빈 문자열 하나를 가지고 시작한다. 플레이어는 이 빈 문자열에 대해 다음의 세가지 연산을 수행할 수 있다.

• A : 현재 문자열의 맨 뒤에 0을 붙인다.
• B : 현재 문자열의 맨 뒤에 1을 붙인다.
• C : 지금까지 만들어진 문자열과 똑같은 문자열을 현재 문자열의 맨 뒤에 덧붙인다.

플레이어는 이러한 연산을 적절히 조합해서 새로운 연산 F를 만들 수 있다. 조합된 연산 F는 순서대로 사용한 연산을 나열한 것으로 표기한다. 예를 들어, F=BA라면 이 연산은 주어진 문자열의 맨뒤에 10을 덧붙인다.

이때 퍼즐에는 어떤 목표 문자열 S가 주어지는데, 플레이어가 만든 연산 F를 빈 문자열에 두 번 적용하면, 결과 문자열은 S가 되어야 한다.

예를 들어 문자열 S가 100100이라고 하자. 그러면 플레이어는 빈 문자열에 F를 두 번 적용하면 결과가 100100이 되는 연산 F를 정의해야 한다. 이때 연산 F=BAA라고 정의하면 빈 문자열에 F를 두 번 적용할 경우 100100이 되므로 이 F는 답이 될 수 있는 연산이다.

이때 조합된 연산 F의 길이(조합에 사용된 연산의 개수)가 짧을 수록 더 높은 점수를 얻게 된다. 현욱을 도와 조건을 만족하는 가장 짧은 F의 길이를 구해보자.

첫째 줄에 목표 문자열 S의 길이 N이 주어진다(1 ≤ N ≤ 1,000,000). 둘째 줄에 목표 문자열 S가 주어진다.

조건을 만족하는 가장 짧은 F의 길이를 출력한다. 그러한 F가 존재하지 않는다면 -1을 출력한다.