백준 1969 - DNA(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1969

1969번: DNA

가장 거리가 작은 DNA를 찾은 뒤, 입력된 DNA들과의 거리 차이를 구하는 문제입니다.

 

거리 차이란, X와 Y의 DNA에서 다른 문자가 몇개인지를 찾는 것입니다.

 

따라서 1~N번까지의 DNA가 주어졌을 때, 1~N번까지의 DNA를 1자리씩 전부 확인합니다.

 

예제 입력을 통해 확인하면

첫번째 DNA는 T T A T T이니 T가 가장 많습니다. 따라서 DNA의 첫자리는 T가 됩니다.

이런 식으로 모든 자리의 DNA를 찾아 완성시켜줍니다.

 

DNA를 찾았다면, 1~N번까지의 DNA와 거리차이를 구해준 뒤, 출력해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;

int N, M;
string dna[1001];
string ans;
int alpha[26];
int Dis = 0;

void get_dna(){
    for(int i = 0; i < M; i++){
        memset(alpha, 0, sizeof(alpha));
        for(int j = 1; j <= N; j++){
            alpha[dna[j][i] - 'A']++;
        }
        int maxi = 0;
        char x;
        for(int j = 0; j < 26; j++){
            if(maxi < alpha[j]){
                maxi = alpha[j];
                x = ('A' + j);
            }
        }
        ans += x;
    }  
}

void get_distance(){
    for(int i = 1; i <= N; i++){
        int x = 0;
        for(int j = 0; j < M; j++){
            if(ans[i] != dna[i][j]) x++;
        }
        Dis += x;
    }
}

void solve(){
    get_dna();
    get_distance();
    cout << ans << "\n" << Dis;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        cin >> dna[i];
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.