시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB203453727.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) 이다.

하지만 아직 정문이는 점수판을 다 만들지 않았다. 점수판은 다음과 같은 규칙으로 만들어야 한다.

  1. 점수판의 모든 원소는 -10보다 크거나 같고, 10보다 작거나 같은 정수이어야 한다.
  2. 점수판은 대각선을 기준으로 대칭형태여야 한다. (Score(X, Y) = Score(Y, X))
  3. 점수판의 대각선 원소는 양수이어야 한다. (Score(X, X) > 0)
  4. 점수판에 있는 16개의 모든 원소의 합은 0이다.

길이가 같은 N개의 문자열이 주어졌을 때, 정문이는 DNA점수의 평균이 최대가 되게 점수판을 만들고 싶다. 예를 들어, N개의 문자열이 주어지면, (N*(N-1))/2개의 쌍의 DNA 점수의 평균을 최대로 해야 한다.

길이가 같은 N개의 문자열이 주어졌을 때, DNA 점수의 평균의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 DNA 문자열의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 문자열이 주어진다. 모든 문자열의 길이는 같으며, 길이의 최댓값은 50이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

예제 입력 1

3
AAA
AAA
AAC

예제 출력 1

30.00

예제 입력 2

2
ACTGACTGACTG
GACTTGACCTGA

예제 출력 2

-4.0

예제 입력 3

4
ACTAGAGAC
AAAAAAAAA
TAGTCATAC
GCAGCATTC

예제 출력 3

50.5

힌트

예제 1의 경우 Score(A, A)와 Score(A, C)를 10으로 만들면, 나머지 원소를 규칙에 맞게 만드는 것은 쉽다. 따라서 모든 세 쌍의 DNA 점수는 30이 된다.

출처

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: dotorya