문제

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

나의 코드

"""
1. 아이디어
자세한 내용은 느낀점에서 참조하고 lcs라는 2차원 배열을 만들어 누적값을 기록 하는게 핵심

2. 시간복잡도
O(2ab) 정도?
"""

from sys import stdin
input = stdin.readline

a = input().rstrip()
b = input().rstrip()

lcs = [ [0] * (len(a)+1) for _ in range(len(b)+1) ]

for i in range(1, len(b)+1):
    for j in range(1, len(a)+1):
        if b[i-1] == a[j-1]: # 가장 최근에 추가된 글자가 서로 같을 때
            lcs[i][j] = lcs[i-1][j-1] + 1 # 두 글자가 추가되기 전 가장 큰 길이 + 1
        else: # 가장 최근에 추가된 글자가 서로 다를 때
            lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]) # 기존에 주어진 문자열로 만들 수 있던 최대 길이

print(lcs[-1][-1])

    

느낀점

처음 풀면 맞출 수 있을까 하는 문제..;;