[백준] 9251-LCS

 

dp 테이블에 일치하는 횟수를 더해준다. count 에는 이전 위치의 최대 값을 저장한다. 

s1= input()
s2=input()
d = [0]*(len(s2))
for i in range(len(s1)):
    count=0
    for j in range(len(s2)):
        if count < d[j]:
            count = d[j]
        elif s1[i] == s2[j]:
            d[j]=count+1
print(max(d))

참고: https://myjamong.tistory.com/317