백준 9251: LCS - dp(Python/파이썬)

두 개의 문자열, str1과 str2를 비교한다.

str1	C	A	T	S	A	R	E	C	U	T	E
str2	D	O	G	S	A	R	E	N	O	T

len(str2) 길이를 가진 배열을 len(str1)개 갖고 있는 이차원 배열 arr을 생성한다.
이 때 arr의 각 인덱스는 다음을 나타낸다.

arr[i][j] == arr[str의 i번 인덱스 알파벳이 ]/[str2의 j번 인덱스 알파벳까지 올 때] 부분 수열 길이

PASS1 str1의 0번 인덱스(C)와 str2의 각 인덱스의 일치도 비교

str1	C	A	T	S	A	R	E	C	U	T	E
str2	D	O	G	S	A	R	E	N	O	T
C ->	0	0	0	0	0	0	0	0	0	0

PASS2 str1의 1번 인덱스(A)와 str2의 각 인덱스 일치도 비교

str1	C	A	T	S	A	R	E	C	U	T	E
str2	D	O	G	S	A	R	E	N	O	T
C->	0	0	0	0	0	0	0	0	0	0
A->	0	0	0	0	1	1	1	1	1	1

PASS3 str1의 2번 인덱스(T)와 str2의 각 인덱스 일치도 비교

str1	C	A	T	S	A	R	E	C	U	T	E
str2	D	O	G	S	A	R	E	N	O	T
C->	0	0	0	0	0	0	0	0	0	0
A->	0	0	0	0	1	1	1	1	1	1
T->	0	0	0	0	0	0	0	0	0	1

PASS4 str1의 3번 인덱스(S)와 str2의 각 인덱스 일치도 비교

str1	C	A	T	S	A	R	E	C	U	T	E
str2	D	O	G	S	A	R	E	N	O	T
C->	0	0	0	0	0	0	0	0	0	0
A->	0	0	0	0	1	1	1	1	1	1
T->	0	0	0	0	0	0	0	0	0	1
S->	0	0	0	1	1	1	1	1	1	1

PASS5 str1의 4번 인덱스(A)와 str2의 각 인덱스 일치도 비교

str1	C	A	T	S	A	R	E	C	U	T	E
str2	D	O	G	S	A	R	E	N	O	T
C->	0	0	0	0	0	0	0	0	0	0
A->	0	0	0	0	1	1	1	1	1	1
T->	0	0	0	0	0	0	0	0	0	1
S->	0	0	0	1	1	1	1	1	1	1
A->	0	0	0	1	2	2	2	2	2	2

PASS6 str1의 5번 인덱스(R)와 str2의 각 인덱스 일치도 비교

str1	C	A	T	S	A	R	E	C	U	T	E
str2	D	O	G	S	A	R	E	N	O	T
C->	0	0	0	0	0	0	0	0	0	0
A->	0	0	0	0	1	1	1	1	1	1
T->	0	0	0	0	0	0	0	0	0	1
S->	0	0	0	1	1	1	1	1	1	1
A->	0	0	0	1	2	2	2	2	2	2
R->	0	0	0	1	2	3	3	3	3	3

이런 식으로 끝까지 반복한다.

이것을 응용해서 2차원 dp배열을 만든다.

이 때, 각 배열의 값은 다음과 같다.

dp[i][j] == str1[:i]와 str[:j]가 가질 수 있는 최대 부분 수열 길이

지금까지는 i와 j가 일치할 때만 카운팅했다면, 이제는 아무튼 str1[i]와 str2[j]를 비교했을 때 그 전에 생성된 모든 부분 수열 중 최대 값을 채워넣는다.

1) str1[i] == str2[j] 일 때
dp[i][j] = dp[i-1][j-1] + 1

2) str1[i] != str2[j] 일 때
dp [i][j] = dp[i-1][j]와 dp[i][j-1] 중 큰 값

---

import sys
input = sys.stdin.readline

str1 = input().strip()
str2 = input().strip()

len1 = len(str1)
len2 = len(str2)
dp = [[0]*(len2 + 1) for _ in range(len1 + 1)] # 0번 인덱스에서 인덱스 에러 방지를 위해 + 1

for i in range(1, len1+1):
    for j in range(1, len2+1):
        if word1[i-1] == word2[j-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[len1][len2])