[BOJ1969] DNA

문제

• DNA [A, T, G, C] 로 이루어짐
• Hamming Distance 는 염기서열에서 다른 분자구조 개수
• hd 합이 최소인 경우의 염기서열 구하기

입력

• N : DNA 수 (1<= <=1,000)
• M : 길이 (1<= <=50)
• 둘째 줄부터 N+1번째 줄까지 DNA

출력

• Hamming distance 합이 가장 작은 DNA(사전순 사장 앞서는 것)
• Hamming distance 합 출력

설계

• [A, C, G ,T] 배열 선언
• Map 이용해서 각 인덱스의 분자구조 개수 체크
• 각 인덱스의 최대 개수의 분자가 최소의 해밍거리 분자
• Result string에 추가 후 나머지 인덱스 개수를 해밍거리에 추가

피드백

• 문제 이해를 잘못해서 각 염기서열이 다른 염기서열과 비교해 해밍거리가 가장 작은 것 구하는 것인 줄 알았음
• 그게 아니라, 특정 염기서열이 주어진 염기서열의 해밍거리 비교하여 그 합이 최소인 것을 구하기
• 그래서 첨에는 백트래킹으로 모든 염기서열을 구한 후, 주어진 염기서열과 해밍거리 비교 —> 당연히 시간초과
• O(nm)으로 가능한 방법 찾고 적용

How I solved(click to github)

---

ref :
BOJ1969