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

 

1969번: DNA

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오

www.acmicpc.net

 

이 문제는 brute force 문제이다

 

DNA 염기 { A, C, G, T } 로 구성된 문자열이 N개 주어졌을 때, 각 자리수의 가장 빈도수가 많은 문자만 뽑으면 된다

 

문제에서는 Hamming distance 등 생소한 용어로 혼란을 주지만 문제 자체만 보면 각 자리수의 빈도수가 가장 높은 문자만

 

뽑으면 그것이 전체 DNA sequence 중 가장 차이가 적은 문자열이 된다

 

counting을 위해서 map 자료구조를 이용했고, 사전 순을 맞추기 위해 max 를 검사할 때 사전 순으로 검사하도록 한다

 

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<vector>
  3. #include<string>
  4. #include<map>
  5. using namespace std;
  6. int n,m;
  7. char buf[55];
  8. char order[4] = { 'A', 'C', 'G', 'T'};
  9.  
  10. int main(){
  11. scanf("%d %d",&n,&m);
  12. vector<string> v;
  13. for(int i=0;i<n;i++){
  14. scanf(" %s", buf);
  15. v.push_back(string(buf));
  16. }
  17. vector< pair<char, int> > ans;
  18. for(int i=0; i<m; i++){
  19. map<char, int> c;
  20. for(int o=0; o<4; o++)
  21. c[order[o]] = 0;
  22. for(int j=0; j<n; j++){
  23. c[v[j][i]] += 1;
  24. }
  25. int max_ = 0, diff = 0;
  26. char d;
  27. for(int o=0; o<4; o++){
  28. diff += c[order[o]];
  29. if(max_ < c[order[o]]){
  30. max_ = c[order[o]];
  31. d = order[o];
  32. }
  33. }
  34. ans.push_back(make_pair(d, diff-max_));
  35. }
  36. int cnt = 0;
  37. for(int i=0;i<ans.size();i++){
  38. printf("%c", ans[i].first);
  39. cnt += ans[i].second;
  40. }
  41. printf("\n%d\n", cnt);
  42. return 0;
  43. }

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24

+ Recent posts