파일 업로드

소 품종 전환기

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

농부 현수의 사촌 현우는 조금 특이한 과학자입니다. 그는 가족 모임에서 많은 갈등을 일으키지만, 농부 현수의 소들과 관련된 문제에 직면했을 때 해결하는 데 도움을 줍니다.

현재 현수는 소들과 관련된 문제를 겪고 있습니다. 그는 최근 NN마리의 소 (1N10001 \leq N \leq 1000)를 주문했는데, 이들은 Holsteins과 Guernsey 두 가지 품종으로 구성되어 있습니다. 그는 주문한 소들을 H(Holsteins을 나타냄) 또는 G(Guernsey를 나타냄)로 구성된 NN개의 문자열로 표시했습니다. 하지만 불행히도, 소들이 그의 농장에 도착하여 줄을 세웠을 때, 그들의 품종은 이 원래 문자열과 다른 문자열을 형성했습니다.

이제 두 문자열을 AABB라고 부르자고 했을 때, 여기서 AA는 현수가 원래 원했던 품종 식별자의 문자열이고, BB는 소들이 도착했을 때 보이는 문자열입니다. 현수가 BB의 소들을 재배열하여 AA를 얻는 것이 충분한지 단순히 확인하는 대신, 그는 사촌 현우에게 과학적 지식을 활용하여 문제를 해결하도록 요청합니다.

몇 달 동안의 작업 끝에 현우는 놀라운 기계, 다중 소 품종 전환기 3000을 만들었습니다. 이 기계는 어떤 소의 부분 문자열이든 선택하고 그 품종을 전환하는 기능을 가지고 있습니다: 부분 문자열에서 모든 H는 G가 되고, 모든 G는 H가 됩니다. 

현수는 현재의 순서 BB를 원래 원했던 순서 AA로 변환하기 위해 이 기계를 최소 몇 번 사용해야 하는지 알고 싶습니다. 

하지만 현우는 독특한 과학 기계를 만들어주기만 할 뿐, 당신이 현수의 문제를 기계를 사용하여 해결하는 데 도움을 주어야합니다.

 

💻 입력

입력의 첫 번째 줄에는 NN이 포함되어 있고, 그 다음 두 줄에는 문자열 AABB가 있습니다. 각 문자열은 H 또는 G로 구성된 NN개의 문자를 가지고 있습니다.

 

🖨️ 출력

BBAA로 변환하기 위해 기계를 적용해야 하는 최소 횟수를 출력합니다.


💻 예제 입력 1
7
GHHHGHH
HHGGGHH
🖨️ 예제 출력 1
2

💡 힌트

첫째로, 현수는 첫 번째 문자에 해당하는 부분 문자열만을 변환할 수 있어, BB를 GHGGGHH로 변환할 수 있습니다. 

그 다음에는, 세 번째와 네 번째 문자로 이루어진 부분 문자열을 변환하면 AA가 됩니다. 

물론, 기계를 두 번 사용하는 다른 조합들도 작동합니다.


출처: USACO 2020 February Contest, Bronze Problem 2. Mad Scientist