Ponk Warshall
시간 제한1초메모리 제한512 MB
길이가 같고 각 문자의 개수가 같은 두 문자열이 주어질 때, 임의의 두 위치를 바꾸는 연산으로 첫 번째 문자열을 두 번째 문자열로 만드는 최소 횟수를 구한다.
문제
록 음악을 들으면 핵 DNA가 순열로 바뀐다. 이 놀랍고 믿기 힘든 사실이 최근 지구 최고의 과학 저널 중 하나인 Rock Nature Weekly에 발표되었다. 연구의 일부로 지원자들에게서 록 콘서트 시즌 전과 후에 DNA 샘플을 채취했다. 샘플을 처리해 여러 유전자를 분리했다. 각 사람에 대해 각 유전자를 두 번 분리했다. 록 시즌 전의 변이와 시즌 후의 변이이다. 이 두 변이를 짝지으면, 많은 경우 한 변이가 짝을 이룬 다른 변이의 순열임을 알 수 있었다.
연구의 다음 단계는 순열이 어떻게 일어나는지 밝히는 것이다. 널리 받아들여지는 가설은 순열이 일련의 자리바꿈, 이른바 스왑으로 이루어진다는 것이다. 스왑은 유전자 안의 정확히 두 염기가 자리를 바꾸는 사건이다(그 화학적 과정은 아직 완전히 밝혀지지 않았다). 유전자 안의 다른 염기는 스왑의 영향을 받지 않는다. 자리를 바꾸는 두 염기의 위치는 완전히 임의일 수 있다.
순열 과정에서 분자의 움직임을 예측하고 관찰하려면, 연구자들은 유전자 안 염기들의 특정 순열을 만들어 내는 스왑 횟수의 이론적 최솟값을 알아야 한다. 핵 DNA 유전자는 염기 시토신, 구아닌, 아데닌, 티민의 배열이며, 각각 C, G, A, T로 표기한다.
입력
입력은 두 줄로 이루어진다. 각 줄은 대문자 “A”, “C”, “G”, “T”로 이루어진 길이 N의 문자열이다(1 ≤ N ≤ 10^6). 두 문자열은 특정 유전자의 한 쌍의 버전을 나타낸다. 첫째 줄은 록 시즌 전의 유전자, 둘째 줄은 같은 사람의 같은 유전자에서 록 시즌 후의 유전자이다. 두 문자열에서 각 염기의 등장 횟수는 같다.
출력
첫 번째 유전자 버전을 두 번째 버전으로 바꾸는 데 필요한 스왑 횟수의 최솟값을 출력한다.