유전체 평가

면접 대비

시간 제한2초메모리 제한512 MB

요약

각 DNA 문자열이 가장 작은 반복 단위로 이루어진 길이를 구한 뒤, 두 점수 집합을 짝지어 제곱 차이의 합이 최소가 되도록 한다.

난이도: 보통10점 중 6점
유형: 문자열, 정렬, 그리디, 문자열 매칭
정답자: 아직 제출이 없습니다

문제

세계는 멸망의 위기에 놓여 있다. 돌연변이 바이러스가 모든 생명체를 파괴할 위협을 가하고 있다. 마지막 희망으로, 물론 당신을 포함한 초똑똑한 과학자 팀이 현재 백신을 개발하고 있다. 안타깝게도 당신의 팀은 제때 DNA를 분석할 수 없다. 팀은 바이러스 DNA의 n개 부분을 염기서열 분석했고, 이를 백신용으로 사용 가능한 n개의 가닥과 짝지어야 한다. 알고리즘 전문가인 당신은 이 문제를 해결할 특별한 절차를 구현해야 한다. 당신의 접근 방식은 빨라야 한다. 남은 시간이 많지 않다!

먼저 각 DNA 서열의 반복 점수를 구해야 한다. 서열 s의 반복 점수는 s가 어떤 양의 정수 k에 대해 서열 u를 k번 반복한 것과 같아지는, 가장 짧은 서열 u의 길이이다. 예를 들어 ATGATG는 ATG를 두 번 반복해 만들 수 있으므로 반복 점수가 3이다. 반면 ATATA는 어떤 진부분 문자열로도 만들 수 없으므로 반복 점수가 5이다.

모든 서열의 점수를 구한 다음에는 n개의 백신 서열과 n개의 바이러스 서열을 짝지어 바이러스가 일으키는 피해를 최소화해야 한다. 두 서열을 짝지었을 때 바이러스가 일으키는 피해는 두 반복 점수의 차의 제곱이다. 예를 들어 백신 서열 ATGATG를 바이러스 서열 ATATA와 짝지으면 (3 − 5)2 = 4 단위의 피해가 발생한다.

DNA 서열을 최적으로 짝지었을 때, 모든 짝에 대한 합으로 계산한 바이러스의 최소 총 피해는 얼마인가?

입력

입력은 다음과 같다.

정수 n (1 ≤ n ≤ 50)이 있는 한 줄. 각각 바이러스와 백신의 DNA 서열 개수이다.
n개의 줄. 각 줄에 바이러스 DNA 서열이 하나씩 있다.
n개의 줄. 각 줄에 백신 DNA 서열이 하나씩 있다.

각 DNA 서열은 길이가 250 이하인 비어 있지 않은 문자열이며, 소문자 a-z와 대문자 A-Z로 이루어진다.

출력

최소 총 피해를 나타내는 정수 하나를 출력한다.

예제2

예제 1
입력
```
2
TTTTTT
TATG
TATATA
AAAGAAAG
```
예상 출력
```
1
```
예제 2
입력
```
3
abcdef
aaa
bab
AbAb
xyzxyz
X
```
예상 출력
```
10
```