'알고리즘 경연 입문 클래식 (제2판)' 연습 문제 3 - 7 DNA 서열 (DNA Consensus String, ACM / ICPC Seoul 2006, UVa 1368)

'알고리즘 경연 입문 클래식 (제2판)' 연습 문제 3 - 7 DNA 서열 (DNA Consensus String, ACM / ICPC Seoul 2006, UVa 1368)
m 개의 길이 가 모두 n 인 DNA 서열 을 입력 하고 DNA 서열 을 구 하 며 모든 서열 의 총 hamming 거 리 는 가능 한 한 작 습 니 다.두 개의 긴 문자열 의 hamming 거 리 는 문자 의 서로 다른 위치 개수 와 같 습 니 다. 예 를 들 어 ACGT 와 GCGA 의 hamming 거 리 는 2 (왼쪽 1, 4 글자 가 다 릅 니 다) 입 니 다.정수 m 와 n (4 & lt; = m & gt; = 50, 4 & gt; = n & gt; = 1000), 그리고 m 개의 길이 가 n 인 DNA 서열 (알파벳 A, C, G, T 만 포함) 을 입력 하고 m 개의 서열 로 출력 되 는 hamming 거리 와 최소 DNA 서열 과 대응 하 는 거 리 를 입력 하 십시오. 다 분해 가 있 으 면 사전 서열 의 최소 해 를 요구 합 니 다.
【 입력 】
T 조 데이터 포함.데 이 터 를 입력 한 첫 번 째 줄 은 T 조 데이터 가 있 을 것 임 을 나타 내 는 정수 T 이다.다음 각 그룹의 데이터 첫 줄 은 두 개의 정수 m 와 n 이 고 m 와 n 사이 에 빈 칸 이 있 습 니 다.그 후에 m 줄 의 DNA 서열 이 있 고 각 줄 의 서열 길 이 는 n 이다.
【 출력 】
각 그룹의 데 이 터 를 두 줄 씩 출력 해 야 합 니 다.첫 번 째 줄 은 구 한 DNA 서열 이 고 두 번 째 줄 은 이 서열 과 본 그룹의 각 줄 데이터 의 hamming 거리의 합 이다.
예제 입력:
3 5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 4 10 ACGTACGTAC CCGTACGTAG GCGTACGTAT TCGTACGTAA 6 10 ATGTTACCAT AAGTTACGAT AACAAAGCAA AAGTTACCTT AAGTTACCAA TACTTACCAA
예제 출력:
TAAGATAC 7 ACGTACGTAA 6 AAGTTACCAA 12
분석 하 다.
처음에 '모든 서열 까지 의 총 hamming 거리 가 가장 작다' 는 서열 에 대해 곤 혹 스 러 웠 는데 나중에 세로 로 보면 된다 는 것 을 알 게 되 었 습 니 다!각 열 에 가장 많은 자모 가 나타 나 는데, 구 성 된 것 이 바로 정확 한 풀이 이다.이 점 을 알 게 된 후 남 은 것 은 세심 한 프로 그래 밍 이다.각 조 의 데이터 간 에는 아무런 관련 이 없 기 때문에 매번 한 조 의 데 이 터 를 저장 하고 처리 하면 됩 니 다. 물론 먼저 정리 하 는 것 을 잊 지 마 세 요!
코드

#include 
#include 
#include 
#include 

char a[55][1050]; //       
char ans[1050]; //         
int count[4]; //       ACGT   

int main()
{
	int t, m, n;
	scanf("%d", &t);
	for(int i=0; i<t; i++) //        
	{
		memset(a, 0, 55*1050); //   
		memset(ans, 0, 1050); //   
		int tot = 0; //                （ hamming   ）
		scanf("%d%d", &m, &n);
		for(int j=0; j<m; j++) //   m      a
			scanf("%s", a[j]);
		for(int j=0; j<n; j++) //         
		{
			count[0]=0; count[1]=0; count[2]=0; count[3]=0; //   
			for(int l=0; l<m; l++) //           
			{
				if(a[l][j]=='A') count[0]++;
				else if(a[l][j]=='C') count[1]++;
				else if(a[l][j]=='G') count[2]++;
				else if(a[l][j]=='T') count[3]++;
			}
			int max=0;
			char maxc;
			for(int x=1;x<4;x++) //               ，             （      ）
				if(count[max]<count[x]) max = x;
			switch(max){ //        maxc
				case 0:maxc = 'A'; break;
				case 1:maxc = 'C'; break;
				case 2:maxc = 'G'; break;
				case 3:maxc = 'T'; break;
			}
			ans[j] = maxc; //           
			for(int x=0; x<m; x++) //              
				if(a[x][j] != maxc) tot++;
		}
		for(int j=0;j<n;j++) printf("%c", ans[j]); //      
		printf("
%d
", tot);
	}
	return 0;
}