백준/ Gold 5 문제 , 백준 파이썬 9251 , LCS

백준/ Gold 5 문제 , 백준 파이썬 9251 , LCS

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

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

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제이다.

 

 

<문제 출처>

 

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

9251번: LCS

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

 

 

문제의 예시인 

 

ACAYKP
CAPCAK

 

입력을 확인해보자.

 

 

 

 

 

\	0	A	C	A	Y	K	P
0	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	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

 

 

첫번째 입력인 ACAYKP 를 기준으로 두번째 입력인 CAPCAK 를 하나씩 비교해나아가며, 표를 작성해 본다.

 

처음 C는 C를 만난 시점부터 쭉 1의 길이다.

 

CA는 A를 만났을때는 1, C를 만났을때도 1 그 후  A를 만나게 되면 CA 로 길이가 2가 된다.

 

CAP 는 P를 만났을때 3까지 증가하게 되고

 

CAPC는 AC에서 윗칸들보다 더 빨리 2에 도달하게 된다.

 

이렇게 작성하다보면 규칙이 보이는데

 

알파벳이 서로 같은 칸은 대각선에서 +1을 한 값과 같다.

 

또한, 알파벳이 서로 다른 칸은 그 칸을 기준으로 윗칸이랑 왼쪽 칸 중에서 큰 값과 같다.

 

이것을 코드로 작성해보면,

 

 

 

이렇게 쓸 수 있겠다.

 

 

마지막으로 표의 마지막 칸이 가장 긴 값이 저장될 것이므로 그 값을 출력해주면 된다.

 

 

 

만약 긴 글과 짧은 글이 만나게 된다면?

 

예를들어, ABCDEF 와 C 를 보자

 

\	0	A	B	C	D	E	F
0	0	0	0	0	0	0	0
C	0	0	0	1	1	1	1

 

 

이런식으로 작성될 수 있겠다.

 

 

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

정답

 

 

 

A=list(input())
B=list(input())
check=[[0 for _ in range(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]:
            check[i][j]=check[i-1][j-1]+1
        else:
           check[i][j]=max(check[i-1][j],check[i][j-1])

print(check[-1][-1])