문제 링크

2306 - 유전자

문제 설명

DNA는 a,c,g,t로 이루어진 문자열이다.

KOI 유전자는

1. at와 gt는 가장 짧은 길이의 KOI 유전자
2. X가 KOI 유전자이면 aXt와 gXc도 KOI 유전자이다.
3. X와 Y가 KOI 유전자이면 XY도 KOI 유전자이다.

KOI 유전자가 DNA 서열의 임의의 0개 이상 문자를 삭제해서 얻어지는 부분서열이라고 할때, 길이가 최대가 되는 KOI 유전자를 구하시오

문제 풀이

dp에서 유명한 유형인 DNA 서열,,, 3학년 알골시간 중간고사에도 나왔던 걸로 기억 ,, 하지만 DP는 역시 쉽지않내요,,

Top-Down 방식으로 풀었다.
주어진 DNA 서열에 대해서

1. (앞,뒤)의 쌍이 ('a','t')이거나 ('g','c')이면 앞+1, 뒤-1로 재귀
2. 1 검사하고 주어진 서열 길이만큼 (앞,i), (i+1,뒤)가 KOI 서열을 만족하는지 재귀를 돈다.

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))

참고

https://www.crocus.co.kr/964