Baekjoon 2306

in Study / Computer science on Baekjoon 2306

dynamic programming

Baekjoon 2306

Description

DNA 서열은 4개의 문자 {a,c,g,t} 로 이루어진 문자열이다. DNA 서열에는 생명의 신비를 풀 수 있는 많은 정보가 들어 있다. 특히 KOI 유전자의 길이는 사람의 키와 깊은 상관 관계가 있다는 것이 알려져 있다. 이러한 KOI 유전자는 다음의 조건을 만족한다.

  1. at 와 gc 는 가장 짧은 길이의 KOI 유전자이다.
  2. 어떤 X가 KOI 유전자라면, aXt와 gXc도 KOI 유전자이다. 예를 들어, agct 와 gaattc는 KOI 유전자이나, tgca 와 cgattc는 KOI 유전자가 아니다.
  3. 어떤 X와 Y가 KOI 유전자라면, 이 둘을 연결한 XY도 KOI 유전자이다. 예를 들면, aattgc 또는 atat는 KOI 유전자이나 atcg 또는 tata는 KOI 유전자가 아니다.

KOI 유전자는 DNA 서열 중에서 부분 서열로 구성되어 있다. 부분 서열이란 주어진 서열에서 임의의 위치에 있는 0개 이상의 문자들을 삭제해서 얻어지는 서열이다. 예를 들면, DNA 서열 acattgatcg에서 두 번째 문자 c와 마지막 문자 g를 삭제하여 생긴 부분 서열 aattgatc는 길이가 8인 KOI 유전자이다. 그러나 마지막 문자 g를 삭제하여 만들어진 부분 서열 acattgatc는 KOI 유전자가 아니다.

문제는 주어진 DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI 유전자를 찾아 그 길이를 출력하는 것이다.

Input

첫째 줄에는 분석하고자 하는 DNA 서열이 주어진다. DNA 서열의 길이는 최대 500이다.

Output

입력 DNA 서열로부터 계산된 가장 긴 KOI 유전자의 길이를 첫 번째 줄에 출력한다. 단, KOI 유전자가 없는 경우에는 0을 출력한다.

Example I & O

Input 1
acattgagtc

Output 1
8

Input 2
aattgatc

Output 2
8

Input 3
aggcggccatatgacc

Output 3
14

Input 4
gcaaattct

Output 4
8

My solution

seq = input()
base_l = []
for i in seq:
    base_l.append(i)

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

for i in range(len(base_l) - 2, -1, -1):
    rowBase = base_l[i]
    for j in range(0, len(base_l)):
        columnBase = base_l[j]
        if i >= j:
            dp[i][j] = 0
            continue
        if rowBase == 't' or rowBase == 'c':
            dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
            continue
        if rowBase == 'g' and columnBase == 't':
            maxValue = dp[i][j-1]
            for k in range(j, i - 1, -1):
                if base_l[k] == 'a':
                    if maxValue < dp[k][j] + dp[i][k-1]:
                        maxValue = dp[k][j] + dp[i][k-1]
                        break

            dp[i][j] = max(maxValue, dp[i+1][j])
            continue

        if rowBase == 'a' and columnBase == 'c':
            maxValue = dp[i][j-1]
            for k in range(j, i - 1, -1):
                if base_l[k] == 'g':
                    if maxValue < dp[k][j] + dp[i][k-1]:
                        maxValue = dp[k][j] + dp[i][k-1]
                        break

            dp[i][j] = max(maxValue, dp[i+1][j])
            continue

        if rowBase == 'a' and columnBase == 't':
            maxValue = dp[i][j-1]

            for k in range(j, i - 1, -1):
                if base_l[k] == 'a':
                    if maxValue < dp[k][j] + dp[i][k-1]:
                        maxValue = dp[k][j] + dp[i][k-1]
                        break

            dp[i][j] = max(dp[i + 1][j - 1] + 2, maxValue, dp[i+1][j])
            continue

        if rowBase == 'g' and columnBase == 'c':
            maxValue = dp[i][j-1]

            for k in range(j, i - 1, -1):
                if base_l[k] == 'g':
                    if maxValue < dp[k][j] + dp[i][k-1]:
                        maxValue = dp[k][j] + dp[i][k-1]
                        break
            dp[i][j] = max(dp[i + 1][j - 1] + 2, maxValue, dp[i+1][j])
            continue

        else:
            dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
            continue

if len(base_l) == 0:
    print(0)
else:
    print(dp[0][len(base_l)-1])

  • Sketch 그림1
    그림2

  • Code Analysis

seq = input()
base_l = []
for i in seq:
    base_l.append(i)

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

base_l → List for individual base
Dp table formation

for i in range(len(base_l) - 2, -1, -1):
    rowBase = base_l[i]
    for j in range(0, len(base_l)):
        columnBase = base_l[j]

i : row index of dp table
j : column index of dp table
그림3

if i >= j:
  dp[i][j] = 0
  continue

By definition of this dp table, dp[i][j] == 0 when i >= j

if rowBase == 't' or rowBase == 'c':
  dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
  continue

When rowBase == pyrimidine, dp[i][j] value is equal to dp[i+1][j].
(because start != pyrimidine in KOI gene)

※ All dp[i][j] >= dp[i + 1][j] and All dp[i][j] >= dp[i][j - 1]

if rowBase == 'g' and columnBase == 't':
    maxValue = dp[i][j-1]
    for k in range(j, i - 1, -1):
        if base_l[k] == 'a':
            if maxValue < dp[k][j] + dp[i][k-1]:
                maxValue = dp[k][j] + dp[i][k-1]
                break

    dp[i][j] = max(maxValue, dp[i+1][j])
    continue

Consider KOI Case number 6
그림4
should find maximum KOI length
→ candidate : dp[i + 1][j], dp[i][j - 1] (by maxValue), number 6 KOI length (by maxValue)

if rowBase == 'a' and columnBase == 'c':
    maxValue = dp[i][j-1]
    for k in range(j, i - 1, -1):
        if base_l[k] == 'g':
            if maxValue < dp[k][j] + dp[i][k-1]:
                maxValue = dp[k][j] + dp[i][k-1]
                break

    dp[i][j] = max(maxValue, dp[i+1][j])
    continue

Consider KOI Case number 5
Method for number 5 KOI length is same with number 6
should find maximum KOI length
→ candidate : dp[i + 1][j], dp[i][j - 1] (by maxValue), number 5 KOI length (by maxValue)

if rowBase == 'a' and columnBase == 't':
    maxValue = dp[i][j-1]

    for k in range(j, i - 1, -1):
        if base_l[k] == 'a':
            if maxValue < dp[k][j] + dp[i][k-1]:
                maxValue = dp[k][j] + dp[i][k-1]
                break

    dp[i][j] = max(dp[i + 1][j - 1] + 2, maxValue, dp[i+1][j])
    continue

Consider KOI Case number 2
Method for number 2 KOI length is same with number 6
Consider KOI Case number 1
그림5
should find maximum KOI length
→ candidate : dp[i + 1][j], dp[i][j - 1] (by maxValue), number 2 KOI length (by maxValue), number 1 KOI length

if rowBase == 'g' and columnBase == 'c':
    maxValue = dp[i][j-1]

    for k in range(j, i - 1, -1):
        if base_l[k] == 'g':
            if maxValue < dp[k][j] + dp[i][k-1]:
                maxValue = dp[k][j] + dp[i][k-1]
                break
    dp[i][j] = max(dp[i + 1][j - 1] + 2, maxValue, dp[i+1][j])
    continue

Consider KOI Case number 4
Method for number 4 KOI length is same with number 6
Consider KOI Case number 3
Method for number 3 KOI length is same with number 1
should find maximum KOI length
→ candidate : dp[i + 1][j], dp[i][j - 1] (by maxValue), number 4 KOI length (by maxValue), number 3 KOI length

else:
    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
    continue

rest of combination between start base (base_l[i]) and end base (base_l[j])

if len(base_l) == 0:
    print(0)
else:
    print(dp[0][len(base_l)-1])

If input == ‘’, I print 0 (not necessary)
Final result == dp[0][len(base_l) - 1]

Best answer

answer
more concise code

© 2017. All rights reserved.

Powered by Hydejack v조현진