[백준]: 1969번: DNA / 탐욕적 기법(Greedy Algorithm)

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

초기에 해당문제를 이해하지못해, 오랜 시간을 허비한 이후에 

http://blog.naver.com/PostView.nhn?blogId=occidere&logNo=220857781286&categoryNo=0&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

블로그를 통해서 정보를 얻은 후에 해결하였다.

// 해밍거리가 같을 경우 사전 순으로 출력하라고 했으므로 change함수에서 A->C->G->T의 사전 순서를 지켜준 이후 RETURN하면 해결된다.

#include<iostream>

using namespace std;

#include<algorithm>

int n, m, Max, hd;

char DNA[1050][1050];

char change(int a, int t, int g, int c, int Max)

{

if (Max == a)return 'A';

else if (Max == c)return 'C';

else if (Max == g)return 'G';

else return 'T';

}

int main()

{

ios::sync_with_stdio(false);

cin.tie(0);

int a, t, g, c;

cin >> n >> m;

for (int i = 0; i < n; i++)

cin >> DNA[i];

for(int i=0;i<m;i++)

{

a = 0, t = 0, g = 0, c = 0;

for (int j = 0; j < n; j++) {

switch (DNA[j][i])

{

case 'A':a++; break;

case 'T':t++; break;

case 'G':g++; break;

case 'C':c++; break;

}

}

Max = max(a, max(t, max(g, c)));

hd += (n - Max);

cout << change(a, t, g, c, Max);

}

cout << "\n";

cout << hd<<"\n";

return 0;

}