백준 9251 python 파이썬 LCS : 최장 공통 부분 수열 @@황소처럼 우직하게@@ 꼭 알아야되는 코딩문제

기본적으로 다음과 같은 표를 만드세요

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0
A	0
P	0
C	0
A	0
K	0

그리고 한줄씩 채워 나갑니다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0
A	0
P	0
C	0
A	0
K	0

위에 테이블에서, C와 A를 비교하면 다르죠?

다르면 max(그 칸의 윗 칸 값, 그 칸의 왼쪽 칸 값) 을 넣어줍니다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1
A	0
P	0
C	0
A	0
K	0

위에 테이블에서, C와 C 같죠?

같으면 (그 칸의 왼쪽 위 대각선 칸 값) 을 넣어줍니다.

이게 답니다. 한줄씩 채워나가면됩니다.

a = input()
b = input()

dp = [[0 for i in range(len(a) + 1)] for j in range(len(b) + 1)]

for i in range(1, len(b) + 1):
    for j in range(1, len(a) + 1):
        if a[j - 1] == b[i - 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])

 

빠르게 솔루션을 소개해드렸습니다.