[Softeer] HSAT 6회 기출 - 염기서열

문제

<배경>

생명 공학을 연구하는 현생이는 요즘 DNA 염기서열을 연구하고 있다.

DNA 염기서열이란 4종류의 핵염기 a(아데닌), c(사이토신), g(구아닌), t(티민)이 일자로 연결된 가닥이다.

문자열로는 a, c, g, t 네 문자의 나열로 나타낸다.

 

현생이는 인간에게 좋게 작용하는 좋은 염기서열 $N$개를 가지고 있고 이 모든 좋은 염기서열의 길이는 $M$이다.

주어진 좋은 염기서열은 몇 개의 와일드 카드(.)을 가지고 있어, 이 부분에는 a, c, g, t의 어떤 염기가 들어가도 좋은 염기서열로 작용한다고 하자.

 

주어진 좋은 염기서열의 조건을 만족할 수 있는 염기서열을 초염기서열이라고 한다.

그러나 주어진 모든 좋은 염기서열을 만족하는 것은 불가능할 수 있어서, 여러 초염기서열을 만들어서 여러 그룹의 좋은 염기서열을 커버할 수 있도록 하고자 한다.

 

주어진 모든 좋은 염기서열을 커버하기 위해 필요한 최소 갯수의 초염기서열은 몇 개일까?

 

<입력>

 

<출력>

첫 번째 줄에 모든 염기서열을 커버하기 위한 초염기서열의 최소 갯수를 출력한다.

 

<예시>

예제 1번: acgtt와 gctag의 두 가지 초염기서열을 가지고 있다면, acgtt는 a..tt와 a.g.t를 만족할 수 있고 gctag는 gc...와 .c.ag를 만족할 수 있어 모든 염기서열을 커버할 수 있다.

---

풀이

이전글에서 HSAT이 오히려 난이도가 낮은 것 같다고 했더니 바로 어려운 문제가 나왔다.

 

조건에서 n이 굉장히 작다. 따라서 $O(2^n)$같은 알고리즘도 사용해볼 수 있다.

 

n,m=map(int,input().split())
dna = []
for _ in range(n):
    dna.append(list(input()))

superDNA = [None for _ in range(2**n)]
superDNA[0] = ['.']*m

for i in range(1,2**n): #O(2**n * (n+m))
    genSuperDNA(i)

answer = [n+1]*(2**n)
answer[0] = 0

for i in range(1,2**n):
    if superDNA[i] != []:
        answer[i]=1
    else:
        genAnswer(i)

print(answer[2**n-1]) #모든 bit가 1일 때의 값

어떤 초염기서열이 입력으로 주어진 n개의 줄의 염기서열에서 몇번째 줄에 있는 것을 포함할 수 있는지 0,1로 나타내보자.

예를 들면 예시1번에서 1010이라면 a..tt, a.g.t를 만족하는 것이다.

이 이진수 값을 십진수로 저장한 것이 index이다.

1부터 2^n-1까지 i를 순회하며 genSuperDNA(i)라는 함수를 호출한다.

즉 가능한 모든 주어진 배열의 조합을 살펴보는 것이다.

 

그럼 genSuperDNA(i)라는 함수가 어떤 함수인지 살펴보자.

파라미터로 들어온 index의 가장 오른쪽 1의 위치를 loc에 저장한다.

예를 들어 index가 14=1110이라면 4개의 입력 서열 중 1,2,3번의 서열을 포함하는 서열을 구하겠다는 것이고,

이를 merge(입력의 3번째 염기서열, 1,2번 서열을 합친 염기서열)로 계산한다는 것이다.\

def genSuperDNA(index):#O(n+m)
    loc = 0 #맨 오른쪽 1
    tempIndex = index
    while tempIndex%2==0:#1110에서 loc은 가장 오른쪽 1의 위치 #O(n)
        loc += 1
        tempIndex = tempIndex//2
    superDNA[index] = merge(dna[loc],superDNA[index-2**loc])

 

merge함수는 간단하다.

두 서열을 받아 이를 포함할 수 있는 초염기서열을 리턴한다.

불가능하면 빈 리스트를 리턴한다.

def merge(dna1,dna2): #O(m)
    if dna1 == [] or dna2 == []:
        return []
    dna = []
    for i in range(m):
        if dna1[i]=='.':
            dna.append(dna2[i])
        elif dna2[i]=='.':
            dna.append(dna1[i])
        elif dna1[i]==dna2[i]:
            dna.append(dna1[i])
        else:
            return []
    return dna

 

 

다음은 getAnswer함수이다.

index로 주어진 염기서열들의 집합을 포함하기 위한 최소한의 초염기서열 개수를 출력한다.

현재 index에 1로 표시된 위치를 bit1리스트를 통해 기억한다.

따라서 len(bit1)은 index안의 1의 개수가 될 것이다.

number1과 number2는 둘이 더하면 index가 된다.

즉 index로 받은 숫자를 두 숫자로 나눠 각 숫자에 대해 genAnswer를 취해 더하는 것이다.

def genAnswer(index): #O(3^n)
    if answer[index] <n+1:
        return answer[index]
    
    bit1 =[] #1이 있는 위치 기억
    number1=number2=0
    tempIndex =index
    for i in range(n):
        if tempIndex%2 == 1:
            bit1.append(i)
            number2+=2**i

        tempIndex = tempIndex//2
    digit = [0] * len(bit1)
    for i in range(1, 2**(len(bit1)-1)):
        for j in range(len(bit1)):
            if digit[j]==1: #이진수 덧셈 1이면 0으로 만들기
                digit[j] = 0
                temp = 2**bit1[j]
                number1 -=temp
                number2 +=temp
            else: #이진수 덧셈 0이면 1로 만들기
                digit[j] = 1
                temp = 2**bit1[j]
                number1 +=temp
                number2 -=temp
                break
        temp = genAnswer(number1)+genAnswer(number2)

        if answer[index]>temp:
            answer[index] = temp
    return answer[index]