백준 7346 - 유전자 함수 (Python)

문제 정보

• https://www.acmicpc.net/problem/7346
• DP

---

문제 정리

각 테스트케이스마다 유전자 서열 A와 B가 주어진다. 유전자 서열의 곳곳에 *을 추가할 수 있으며, 문제에 나온 표에 따라 두 유전자 서열의 유사도를 계산할 수 있다. 이 *을 적절히 추가할 때, 가능한 유사도의 최대값을 구해야 한다.

---

풀이

딱 봐도 DP이다. 부분 문제는 각 문자열을 어디까지 비교했는지로 잡으면 된다.

DP[i][j] = 유전자 A를 i번째까지 비교했고 유전자 B를 j번째까지 비교했을 때, 유사도의 최대값

이렇게 점화식을 세우고 (A와 *을 매칭하는 경우), (*와 B를 매칭하는 경우), (A와 B를 매칭하는 경우) 총 세 가지를 고려하면서 계산하면 $O(N^2)$으로 해결할 수 있다.

G2가 아니라 G3같다. 기여창을 보니 LCS DP와 비슷하다고 하는데 LCS 풀이가 잘 기억이 안나서 모르겠다.

---

코드

# 백준 7346

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline
t = {'A': 0, 'C': 1, 'G': 2, 'T': 3, '*': 4}
value = [(5, -1, -2, -1, -3),
        (-1, 5, -3, -2, -4),
        (-2, -3, 5, -2, -2),
        (-1, -2, -2, 5, -1),
        (-3, -4, -2, -1, -10**8)]


def solve(A, B):
    lenA = len(A)
    lenB = len(B)
    DP = [[0 for _ in range(lenB+1)] for _ in range(lenA+1)]
    
    # DP 초기값 계산
    for y in range(1, lenA+1):
        DP[y][0] = DP[y-1][0] + value[A[y-1]][4]
    for x in range(1, lenB+1):
        DP[0][x] = DP[0][x-1] + value[4][B[x-1]]

    for y in range(1, lenA+1):
        for x in range(1, lenB+1):
            # A와 *을 매칭하는 경우, *과 B를 매칭하는 경우, A와 B를 매칭하는 경우
            DP[y][x] = max(DP[y-1][x] + value[A[y-1]][4], DP[y][x-1] + value[4][B[x-1]], DP[y-1][x-1] + value[A[y-1]][B[x-1]])

    return DP[lenA][lenB]


def main():
    T = int(input())
    for _ in range(T):
        _, A = input().decode().split()
        _, B = input().decode().split()
        A = [t[i] for i in A]
        B = [t[i] for i in B]

        print(solve(A, B))


main()