백준 | [파이썬 Python] 9251 LCS

 

코드

first_string = input()
second_string = input()
h,w = len(first_string), len(second_string)
cache = [[0]*(w+1) for _ in range(h+1)]

for i in range(1, h+1):
    for j in range(1, w+1):
        if first_string[i-1] == second_string[j-1]:
            cache[i][j] = cache[i-1][j-1]+1
        else:
            cache[i][j] = max(cache[i][j-1], cache[i-1][j])
print(cache[-1][-1])

 

 

설명

두 개의 string을 2차원 배열로 비교하는 것으로 접근하면 된다

ACAYKP
CAPCAK

    A C A Y K P

C  0, 1, 1, 1, 1, 1

A  1, 1, 1, 2, 2, 2

P 1, 2, 2, 2, 3, 3

C 1, 2, 2, 2, 3, 3

A 1, 2, 2, 2, 3, 3

K 1, 2, 2, 2, 3, 4  

 

배운 점