백준 2306 유전자 python

다이나믹 프로그래밍 문제는 풀어도 풀어도 어렵게 느껴진다.
보통 DP 문제는 바텀업 방식으로 풀었는데 이 문제는 탑다운 방식이라 더 어렵게 느껴졌다.

📜 문제 바로 가기 : 유전자

제출코드

파이썬

import sys
input = sys.stdin.readline

# KOI = at, gc
# KOI 유전자 길이 2, 4, 6, 8, ... 는 짝수

myDNA = input().rstrip()
N = len(myDNA)

DP = [[-1] * N for _ in range(N)] # DP[i][j] = i ~ j 까지 DNA 서열에서 최장KOI 길이

def DFS(x, y):
    if x >= y:
        return 0
    
    if DP[x][y] != -1:
        return DP[x][y]
    
    if (myDNA[x] == "a" and myDNA[y] == "t") or (myDNA[x] == "g" and myDNA[y] == "c"):
        DP[x][y] = DFS(x+1, y-1) + 2

    for i in range(x, y):
        DP[x][y] = max(DP[x][y], DFS(x, i) + DFS(i+1, y))
    
    return DP[x][y]

DFS(0, N-1)
print(DP[0][N-1])

---

접근방법

KOI DNA를 만드는 방법이 양끝에 a, t 혹은 g, c를 붙이는 방법 외에 서로 다른 두 KOI DNA를 연결하는 방법이 있는데, 이걸 처리할 방법을 생각하는게 힘들었다.

DP[x][y]가 x ~ y까지의 DNA 서열이 가질 수 있는 최대 KOI DNA길이 를 뜻하기 때문에 슬라이딩 윈도우 처럼 이 사이를 움직이는 i 값을 주고 DP[x][i] + DP[i+1][y] 처리로 DP[x][y] 의 값을 채웠다.