백준 9251번 LCS 파이썬 (python code)

난이도: 골드5
번호: 9251번

 

모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

 

www.acmicpc.net/problem/9251  

9251번: LCS

 

두 글자의 부분수열이 되는 가장 긴 수열을 찾는 문제이다.

예시는 다음과 같다.

 

예시1)

ACAYKP

CAPCAK

--------

ACAK

 

예시2)

ABCDE

CKA

-------

C

 

예시3)

AAAAABCCO

FABORITE

------------

ABO

 

DP로 문제를 해결하고자했다.

먼저 각 단어를 행과 열로 나누고 해당 글자까지 [0:n] 만들 수 있는 글자를 행렬안에 대입하도록 하였다.

 

ACAYKP

CAPCAK

을기준으로 

	_	A	C	A	Y	K	P
_	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0
C	0
A	0
K	0

으로 초기화 시킨 다음 계산을 시작한다.

열을 먼저 증가시키고 행을 증가시키는 방향으로 계산하는데

먼저 A와 C는 동일한 글자가 아니므로0

AC와 C 는 동일한 글자가 있다 따라서 1

ACA와 C도 1  ACAYK & C 1    ACAYKP & C 1

이된다.

다음으로는 CA와 비교를 진행하는데

이전 (C와 비교)를 참조하자.

 

결론적으로

1.행렬값의 최소는 양쪽 이전값 (matrix[i][j-1],matrix[i-1][j]) 의 최대이다.

2.마지막 값이 같으면 그 대각선 전(matrix[i-1][j-1])값 +1이다.

 

따라서 이를 파이썬으로 작성하면

 

import sys

word1 = list(sys.stdin.readline().rstrip())[:]
word2 = list(sys.stdin.readline().rstrip())[:]

idx1, idx2=0,0
len1, len2= len(word1)+1, len(word2)+1
lcs= [[0]*len2 for _ in range(len1)]
for i in range(1,len1):
    for j in range(1,len2):
        if word1[i-1]==word2[j-1]:
            lcs[i][j] = lcs[i-1][j-1]+1
        else:
            lcs[i][j] = max(lcs[i][j-1],lcs[i-1][j])
print(lcs[len1-1][len2-1])