2022.02.14 [백준] (python 파이썬) DNA

 

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

1969번: DNA

---

풀이

출처 : https://kongpowder.tistory.com/74

처음 이 문제를 이해하기가 어려웠다. 그래서 구글링 중, 위 그림을 발견하였다. 위의 그림처럼 같은 위치에 있는 DNA중 가장 많이 나온 DNA와 그 DNA를 제외하고 나온 DNA의 갯수를 모두 더해주면 답을 구할 수 있다.

이 문제는 각 상황에서의 최선을 찾는 문제이기 때문에 그리디 알고리즘을 사용할 수 있다.

n,m=map(int, input().split())
str=[]
for i in range(n):
    str.append(input())
 
dna=['A','C','G','T']
result=''
num=0
for i in range(m):
    cnt=[0,0,0,0]
    for j in range(n):
        if str[j][i]=='A':
            cnt[0]+=1
        elif str[j][i]=='C':
            cnt[1]+=1
        elif str[j][i]=='G':
            cnt[2]+=1
        elif str[j][i]=='T':
            cnt[3]+=1
        idx= cnt.index(max(cnt))
    result+=dna[idx]
    num+=(n-max(cnt))
 
print(result,num,sep="\n")