레이팅 미적용농부 존의 사촌 벤은 하필이면 매드 사이언티스트다. 보통은 가족 모임에서 상당한 마찰을 일으키지만, 특히 농부 존이 소들과 관련해 독특하고 특이한 문제에 직면했을 때는 가끔 도움이 되기도 한다.
농부 존은 지금 소들과 관련해 독특하고 특이한 문제에 직면해 있다. 그는 최근 홀스타인과 건지라는 두 가지 품종으로 이루어진 \(N\)마리의 소(\(1 \leq N \leq 1000\))를 주문했다. 그는 주문서에 소들을 \(N\)개의 문자로 이루어진 문자열로 명시했는데, 각 문자는 H(홀스타인) 또는 G(건지)이다. 안타깝게도 소들이 농장에 도착해 줄을 세워 보니, 품종이 원래 문자열과 다른 문자열을 이루고 있었다.
이 두 문자열을 \(A\)와 \(B\)라고 하자. \(A\)는 농부 존이 원래 원했던 품종 식별자 문자열이고, \(B\)는 소들이 도착했을 때 그가 본 문자열이다. \(B\)의 소들을 단순히 재배열해서 \(A\)를 얻을 수 있는지 확인하는 대신, 농부 존은 사촌 벤에게 그의 과학적 재능으로 이 문제를 해결해 달라고 부탁한다.
여러 달의 작업 끝에 벤은 놀라운 기계인 다품종소반전기 3000을 만들어냈다. 이 기계는 소들의 임의의 부분 문자열을 잡아 그 품종을 반전시킬 수 있다. 즉, 해당 부분 문자열 안의 모든 H는 G가 되고 모든 G는 H가 된다. 농부 존은 현재 배열 \(B\)를 원래 원하던 배열 \(A\)로 바꾸기 위해 이 기계를 최소 몇 번 적용해야 하는지 알아내고 싶다. 안타깝게도 벤의 매드 사이언티스트 실력은 기발한 장치를 만드는 것 이상으로는 미치지 못하므로, 여러분이 농부 존을 도와 이 계산 난제를 해결해야 한다.
문제 제공: Brian Dean
문제 제공: Brian Dean
입력의 첫째 줄에 \(N\)이 주어지고, 다음 두 줄에 문자열 \(A\)와 \(B\)가 주어진다. 각 문자열은 H 또는 G인 \(N\)개의 문자로 이루어져 있다.
\(B\)를 \(A\)로 바꾸기 위해 기계를 적용해야 하는 최소 횟수를 출력한다.
breedflip.in · 출력을 쓸 파일 breedflip.out7
GHHHGHH
HHGGGHH2First, FJ can transform the substring that corresponds to the first character
alone, transforming \(B\) into GHGGGHH. Next, he can transform the substring
consisting of the third and fourth characters, giving \(A\). Of course, there
are other combinations of two applications of the machine that also work.
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > February > Bronze