DNA는 a,c,g,t로 이루어진 문자열이다.
KOI 유전자는
KOI 유전자가 DNA 서열의 임의의 0개 이상 문자를 삭제해서 얻어지는 부분서열이라고 할때, 길이가 최대가 되는 KOI 유전자를 구하시오
dp에서 유명한 유형인 DNA 서열,,, 3학년 알골시간 중간고사에도 나왔던 걸로 기억 ,, 하지만 DP는 역시 쉽지않내요,,
Top-Down 방식으로 풀었다.
주어진 DNA 서열에 대해서
import sys
input = sys.stdin.readline
def findKOI(start, end):
isKOI = dp[start][end]
if isKOI != -1:
return isKOI
isKOI = 0
# 조건 2: aXt, gXc 인지?
if((dna[start] == 'a' and dna[end] == 't') or (dna[start] == 'g' and dna[end] == 'c')):
isKOI = findKOI(start+1, end-1) + 2;
for i in range(start, end):
isKOI = max(isKOI, findKOI(start, i) + findKOI(i+1, end))
dp[start][end] = isKOI
return isKOI
dna = input()
dp = [[-1 for _ in range(len(dna))] for _ in range(len(dna))]
print(findKOI(0, len(dna)-1))