[BOJ] 2306 - 유전자 (Python)

 

 

아이디어

 

동적 계획법으로 부분 서열들 중 KOI 유전자의 최대 길이를 저장해 나간다.

 

 

풀이

 

dp[i][j]는 인덱스 i부터 j까지의 DNA 서열에서 가장 긴 KOI 유전자 길이를 저장한다.

 

def solution():
    DNA = input()
    N = len(DNA)
    dp = [[0]*N for _ in range(N)]
    for j in range(1, N):
        for i in range(j-1, -1, -1):
            if (DNA[i] == 'a' and DNA[j] == 't') or (DNA[i] == 'g' and DNA[j] == 'c'):
                dp[i][j] = dp[i+1][j-1]+2
            for k in range(i, j):
                if dp[i][k]+dp[k+1][j] > dp[i][j]:
                    dp[i][j] = dp[i][k]+dp[k+1][j]
    print(dp[0][N-1])

solution()