백준 1969번 : DNA
1969번: DNA
DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오
www.acmicpc.net
구해야 하는 DNA를 S라고 하면, S의 0번째 문자부터 M-1번째 문자를 정해야 한다.
N개의 DNA의 k번째 문자들 중 가장 많이 등장한 문자가 S의 k번째 문자가 된다.
예를 들어,
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
와 같이 5개의 DNA가 있다고 하자.
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
5개의 DNA의 0번째 문자가 T,T,A,T,T 이고, 이 중에 T가 가장 많이 등장했으므로 S의 0번째 문자는 T가 된다.
그래야 Hamming Distance를 최소로 만들 수 있기 때문이다.
그리고 이 때 0번째 문자에서의 Hamming Distance는 N - T의 개수 = 1개가 된다.
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
1번째 문자도 마찬가지로 A,A,A,G,A 중에서 A가 가장 많이 등장했으므로 S의 1번째 문자는 A가 되고,
여기서 Hamming Distance는 1개이다.
이런식으로 나머지 k번째 문자들을 비교해서 가장 많이 등장한 문자를 S의 k번째 문자로 지정한다.
소스코드 :
'BOJ' 카테고리의 다른 글
| [백준 16194번] 카드 구매하기 2 (java) (0) | 2021.02.23 |
|---|---|
| [백준 9184번] 신나는 함수 실행 (java) (0) | 2021.02.23 |
| [백준 2841번] 외계인의 기타 연주 (java) (0) | 2021.02.20 |
| [백준 1935번] 후위 표기식2 (java) (0) | 2021.02.20 |
| [백준 17298번] 오큰수 (java) (2) | 2021.02.20 |