[Python] 백준 2306번: 유전자

https://www.acmicpc.net/problem/2306

2306번: 유전자

1. 현재와 끝이 a, t or g, c이면 앞뒤 둘다 자를 수 있고 그렇지 않으면 k인덱스를 기준으로 분할한다.

2. acattgagtc를 기준으로 하였을 때 a cattgagtc, ac attgagtc, aca ttgagtc, acat tgagtc 이런식으로 자를 수 있는데 앞뒤가 조건에 성립하면 acattgagt c 여기서, a cattgag t 앞뒤 한번에 분할할 수 있다.

3. 점화식은 dp[x][y] = min{dp[x][y], dp[x][k] + dp[k+1][y]{ x <= k < y}, dp[x][y],

                                   dp[x+1][y-1]{(t[x] = 'a' and t[y] = 't') or (t[x] = 'g' and t[y] = 'c')}}

import sys
input = sys.stdin.readline

t = input().strip()
dp = [[float('inf') for _ in range(len(t))] for _ in range(len(t))]

def dfs(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    if dp[x][y] != float('inf'):
        return dp[x][y]

    if (t[x] == 'a' and t[y] == 't') or (t[x] == 'g' and t[y] == 'c'):
        dp[x][y] = min(dp[x][y], dfs(x+1, y-1))
    for k in range(x, y):
        dp[x][y] = min(dp[x][y], dfs(x, k) + dfs(k+1, y))

    return dp[x][y]

print(len(t) - dfs(0, len(t)-1))