매드 사이언티스트 timer 2s memory 512MB

Farmer John의 사촌 Ben은 미친 과학자이다. 보통 이런 사실은 가족 모임에서 잦은 갈등을 일으키지만, 가끔은 John이 소들과 관련된 특이하고 이상한 문제를 겪을 때 도움이 되기도 한다.

현재 Farmer John은 소들 때문에 아주 특이하고 이상한 문제를 겪고 있다. 그는 최근 두 품종으로 이루어진 소 N마리를 주문했다. 두 품종은 Holstein과 Guernsey이며, 주문할 때 N개의 문자로 이루어진 문자열을 사용해 각 소의 품종을 지정했다. 이 문자열의 각 문자는 H(Holstein) 또는 G(Guernsey)이다.

하지만 소들이 농장에 도착해 한 줄로 세워 보니, 실제 소들의 품종 순서는 그가 처음 주문할 때 사용한 문자열과는 다른 문자열이 되어 있었다.

이 두 문자열을 각각 A와 B라고 하자.

• A는 Farmer John이 원래 원했던 품종 순서를 나타내는 문자열이고,

• B는 실제로 농장에 도착한 소들을 줄 세웠을 때의 품종 순서를 나타내는 문자열이다.

Farmer John은 단순히 B에 있는 소들의 순서를 재배열해서 A를 만들 수 있는지 확인하는 것 대신, 사촌 Ben의 과학적 재능을 이용해 이 문제를 해결하고 싶어 한다.

몇 달간의 연구 끝에, Ben은 놀라운 기계인 “multi-cow-breed-flipinator 3000”을 만들어냈다. 이 기계는 소들 중 아무 연속 구간 하나를 선택해서, 그 구간에 있는 모든 소의 품종을 토글(toggle)할 수 있다. 즉, 그 구간 안의 모든 H는 G로, 모든 G는 H로 바뀐다.

Farmer John은 이 기계를 최소 몇 번 사용해야 현재의 순서 B를 자신이 원래 원했던 순서 A로 바꿀 수 있는지 알고 싶어 한다. 하지만 Ben의 미친 과학자 능력은 기계를 만드는 데까지만 발휘되었고, 그 이후의 계산 문제는 당신이 해결해야 한다.

문자열 B를 문자열 A로 바꾸기 위해 이 기계를 적용해야 하는 최소 횟수를 구하라.