[파이썬 / 백준 9251번] LCS

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

하루 종일 고민했는데...

결국 풀이를 참고했다.

 

import sys
input=sys.stdin.readline
A=input().upper()
B=input().upper()
a=len(A)
b=len(B)
dp=[[0]*(b) for _ in range(a)]

for i in range(1,a):
    for j in range(1,b):
        if A[i-1]==B[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

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

 

지금까지는 1차원적으로 DP수열에 저장하는것으로 했었는데

이건 또 2차원수열..

 

어떤지 어떻게 해도 답이 안나오더라..

 

하기 블로그 참고해서 이해했다

 

LCS 풀이

[백준알고리즘] 9251번: LCS -Python