시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 203 | 45 | 37 | 27.820% |
DNA 문자열이란 A, C, T, G로만 이루어진 문자열이다. 두 개의 길이가 같은 DNA 문자열이 있을 때, 세준이는 DNA 점수를 구하려고 한다. DNA 점수란 정문이가 만든 4*4 점수판을 이용해서 구한다. 정문이는 점수판의 이름을 Score라고 했다.
DNA 점수는 두 문자열에서 같은 위치에 있는 문자를 뽑아서, 점수판을 이용해서 구한뒤 합하면 된다. 예를 들어서, 두 문자열이 ACTA와 GATC라면, 두 문자열의 DNA 점수는 Score(A, G) + Score(C, A) + Score(T, T) + Score(A, C) 이다.
하지만 아직 정문이는 점수판을 다 만들지 않았다. 점수판은 다음과 같은 규칙으로 만들어야 한다.
길이가 같은 N개의 문자열이 주어졌을 때, 정문이는 DNA점수의 평균이 최대가 되게 점수판을 만들고 싶다. 예를 들어, N개의 문자열이 주어지면, (N*(N-1))/2개의 쌍의 DNA 점수의 평균을 최대로 해야 한다.
길이가 같은 N개의 문자열이 주어졌을 때, DNA 점수의 평균의 최댓값을 구하는 프로그램을 작성하시오.
첫째 줄에 DNA 문자열의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 문자열이 주어진다. 모든 문자열의 길이는 같으며, 길이의 최댓값은 50이다.
첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
3 AAA AAA AAC
30.00
2 ACTGACTGACTG GACTTGACCTGA
-4.0
4 ACTAGAGAC AAAAAAAAA TAGTCATAC GCAGCATTC
50.5
예제 1의 경우 Score(A, A)와 Score(A, C)를 10으로 만들면, 나머지 원소를 규칙에 맞게 만드는 것은 쉽다. 따라서 모든 세 쌍의 DNA 점수는 30이 된다.