백준 1969 - DNA

문제

https://www.acmicpc.net/problem/1969

1969번: DNA

 

풀이

 

열끼리 비교해서 다를 때 Hamming Distance가 발생한다.

따라서 각각의 DNA 문자열에서 열끼리 비교해서 가장 많이 나온 알파벳을 고르면 된다.

그러면 최소의 Hamming Distance가 된다.

 

 

코드

c++

#include <iostream>
 
using namespace std;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int N, M;
    cin >> N >> M;
 
    char DNA[1000][51];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> DNA[i][j];
        }
    }
 
    // ACGT
    int index = 0;
    int count = 0;
 
    char result[51];
    char choice[4] = { 'A', 'C', 'G', 'T' };
 
    for (int i = 0; i < M; i++)
    {
        int ACGT[4] = { 0 };
        for (int j = 0; j < N; j++)
        {
            if (DNA[j][i] == 'A') ACGT[0]++;
            else if (DNA[j][i] == 'C') ACGT[1]++;
            else if (DNA[j][i] == 'G') ACGT[2]++;
            else ACGT[3]++;
        }
 
        int max = 0;
        for (int i = 1; i < 4; i++)
        {
            if (ACGT[max] < ACGT[i])
                max = i;
        }
 
        for (int i = 0; i < 4; i++)
        {
            if (max == i)
                continue;
            count += ACGT[i];
        }
 
        result[index++] = choice[max];
    }
 
    cout << result << '\n' << count;
 
    return 0;
}