접근법

2차원 dp:
재귀 헷갈림. 재귀말고 반복
O(N2)인거 확인했으면 2중 반복문으로 2차원 dp배열 채울 생각 해야함
dp[i] = dp[i-1]에 관한 식으로 정리해야 함.

풀기 전 떠올린 것

'''
두 개가 같이 움직여야할듯
1000글자
1,000 * 1,000
100,000,000

psum[i][j]: A[:i+1] & B[:j+1] 의 lcs를 저장

같을 때
둘다 옮김

다를 때
i를 옮기는 경우
j를 옮기는 경우

a b a 0
a 1 1 1 0
b 1 2 0
c 0
0 0 0 0 0
'''

풀이

2차원 배열 초기화 실수 자주 함

#실수1: 행 열 바뀜
lcs = [[''] * la for _ in range(lb)]  

#실수2: lb*la개 일차원 배열
lcs = ['' for _ in range(lb) for _ in range(la)]  

i-1을 해결하는 기법

1. dp[-1] 리스트 컴프리헨션 사용

a b a 0
a 1 1 1 '
b 1 2 '
c '
0 ' ' ' '

import sys
input = sys.stdin.readline

A = input().strip()
B = input().strip()

la = len(A)
lb = len(B)
lcs = [[""] * (lb+1) for _ in range(la+1)]


for i in range(la):
    for j in range(lb):
        if A[i] == B[j]:
            lcs[i][j] = lcs[i-1][j-1] + A[i]
        else:
            if len(lcs[i][j-1]) > len(lcs[i-1][j]):
                lcs[i][j] = lcs[i][j-1]
            else:
                lcs[i][j] = lcs[i-1][j]
ans = lcs[la-1][lb-1]
print(len(ans))
if len(ans) != 0:
    print(ans)

2. 일반항 0번째에 dummy를 삽입하여 1부터 탐색하도록 맞추기

0 a b a
0 ' ' ' '
a ' 1 1 1
b ' 1 2
c '

import sys
input = sys.stdin.readline

A = '0'+input().strip()
B = '0'+input().strip()

la = len(A) - 1
lb = len(B) - 1
lcs = [['' for _ in range(lb+1)] for _ in range(la+1)]

for i in range(1, la+1):
    for j in range(1, lb+1):
        if A[i] == B[j]:
            lcs[i][j] = lcs[i-1][j-1] + B[j]
        else:
            if len(lcs[i][j-1]) > len(lcs[i-1][j]):
                lcs[i][j] = lcs[i][j-1]
            else:
                lcs[i][j] = lcs[i-1][j]
ans = lcs[la][lb]
print(len(ans))
if len(ans) != 0:
    print(ans)

다른 풀이