[백준]2306 유전자 #grid

1. 풀이

dp[i][j] : i에서 j문자열까지 만들 수 있는 길이 중 최대

dp[i][j]를 구하기 위해선 아래 두가지를 고려해주면 된다.

​

(1) (A[i]==a and A[j]==t) or (A[i]==g and A[j]==c) 인경우 dp[i+1][j-1]+2

=> 양끝이 조건에 만족하면 KOI유전자

​

(2) dp[i][j]=max(dp[i][j-s]+dp[i+j+1-s][j] (k: 1~j-i))

=> () + ()가 가능(각조합에서 최댓값 찾기)

 

2. 소스코드

A=input()
size=len(A)

dp=[[0 for j in range(size)] for i in range(size)]

for j in range(1,size):
    for k in range(size-j):
        dp[k][j + k] = dp[k + 1][j + k - 1]
        #a()t or g()c
        if (A[k]=="a" and A[j+k]=="t") or (A[k]=="g" and A[j+k]=="c"):
            dp[k][j+k]+=2

        #합치기
        for s in range(1,j+1):
            dp[k][j+k]=max(dp[k][j+k],dp[k][j+k-s]+dp[k+(j+1-s)][j+k])

print(dp[0][size-1])