오답노트 - LCS,LCS2

굉장히 오랜만에 블로그에 포스팅했던 문제를 다시 풀어봤다. 역시, 수월하게 풀리지 않았다. dp문제들은 정말 꾸준하게 다시 복습하는 습관을 가져가야할 것 같다.

CODE

import sys
read=sys.stdin.readline

a=read().strip()
b=read().strip()
a='0'+a
b='0'+b
len_a=len(a)
len_b=len(b)
dp=list(list('' for _ in range(len_b)) for _ in range(len_a))

for i in range(1,len_a):
    for j in range(1,len_b):
        dp[i][j]=dp[i-1][j]
        if a[i]==b[j] and j>=len(dp[i][j])+1 :
            dp[i][j]=dp[i-1][j-1]+a[i]
        elif len(dp[i][j])<len(dp[i][j-1]):
            dp[i][j]=dp[i][j-1]
print(len(dp[-1][-1]))
print(dp[-1][-1])


연속합2

연속합을 응용해서 풀 수 있었던 DP 문제였다.

CODE

import sys
read = sys.stdin.readline

n = int(read())

num = list(map(int, read().split()))

dp = list([0, 0] for _ in range(n))
dp[0] = [num[0], num[0]]
answer = num[0]
for i in range(1, n):
    dp[i][0] = max(num[i], dp[i-1][0]+num[i])
    dp[i][1] = max(dp[i][0], dp[i-1][0], dp[i-1][1]+num[i])
    answer = max(answer, dp[i][1])
print(answer)


풀어야 할 문제

  • 스타트 택시🔥🔥
  • 미네랄
  • 아기 상어
  • 전깃줄 -2
  • 치즈🔥
  • 소가 길을 건너간 이유
  • 벽 부수고 이동하기
  • 알 수 없는 문장


```