[백준/파이썬] 1969번 DNA 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1969번 DNA
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

여러 DNA 문자열이 주어질 때 해밍 거리를 최소화하는 대표 DNA 문자열과 그 최소 해밍 거리 합을 구하는 문제입니다.

코드

n, m = map(int, input().split())
a = [0]*m
c = [0]*m
g = [0]*m
t = [0]*m

for _ in range(n):
    dna = input()
    for i in range(len(dna)):
        if dna[i] == 'A': a[i] += 1
        elif dna[i] == 'C': c[i] += 1
        elif dna[i] == 'G': g[i] += 1
        else: t[i] += 1

hd = 0
for i in range(m):
    if a[i] >= c[i] and a[i] >= g[i] and a[i] >= t[i]:
        print('A', end="")
        hd += a[i]
    elif c[i] >= a[i] and c[i] >= g[i] and c[i] >= t[i]:
        print('C', end="")
        hd += c[i]
    elif g[i] >= a[i] and g[i] >= c[i] and g[i] >= t[i]:
        print('G', end="")
        hd += g[i]
    else:
        print('T', end="")
        hd += t[i]
print()

print(n*m-hd)

설명

각 열마다 A/C/G/T 등장 횟수를 세고 가장 많은 문자를 대표 문자열 문자로 선택합니다.

선택된 문자 수의 합을 hd에 누적하면 전체 문자 수 n*m에서 빼서 최소 해밍 거리 합을 구할 수 있습니다.

---

• 백준 문제풀이 전체 목록 보기

---