[1969] DNA

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

1969번: DNA

<문제>

그때그때 가장 많이나온 문자를 그리디적으로 선택하면 된다.

n개의 문자열을, m번에 걸쳐서 하나씩 순회하며 {A G C T} 각각의 개수중 최대를 tar에 저장해두었다면,

최종적인 거리를 구하기 위해서 (n-tar)를 누적합해 나가면 된다.

거리가 같은 문자열이 여러개인 경우, 사전순에 우선해야 한다는 조건이 있는데

string base="ACGT"; 처럼, 구현할때 사전순으로 구현하면 자연스럽게 처리가 가능하다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, dst;
vector<string> v;
string base = "ACGT";
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    v.resize(n);
    int i, j;
    for (i = 0; i < n; i++) cin >> v[i];
    for (i = 0; i < m; i++) {
        vector<int> chk(4, 0);
        for (j = 0; j < n; j++)
            chk[find(base.begin(), base.end(), v[j][i]) - base.begin()]++;
        int tar = max({chk[0], chk[1], chk[2], chk[3]});
        for (j = 0; j < 4; j++) {
            if (chk[j] == tar) {
                cout << base[j];
                break;
            }
        }
        dst += (n - tar);
    }
    cout << '\n' << dst;
    return 0;
}