[백준]9251 LCS(Python)

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

9251번: LCS

 

문제 접근 

 

앞서 푼 dp 문제들과 비슷하지만 이번엔 두 입력을 비교하면서 진행해야 하기 때문에 점화식을 만들 때 이차원 배열로 정의해야할 것 같은 생각이 들었다. 

 

d[i][j] = first의 i 번째와 second의 j 번째 문자를 포함해서 만들 수 있는 부분수열의 최대 길이...?

 

1st: ACAYKP

2nd: CAPCAK

 

1st: A

2nd: C

=> LCS: 0

 

1st: A

2nd: CA

=> LCS: 1

 

1st: A

2nd: CAP

=> LCS: 1

 

... 

 

1st: AC

2nd: C

=> LCS: 1

 

1st: AC

2nd: CA

=> LCS: 1

 

	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

 

First와 Second의 가장 최근(동시)에 추가된 글자가 서로 같을 때, 

dp[3][6] = dp[2][5] + 1 = 2 + 1 = 3 (=>A)

dp[5][7] = dp[4][6] + 1 = 3 + 1 = 4 (=>K)

직관적으로 이해 가능!! 

 

그렇지 않을 때,

CAPCA, ACAYK이면 CAPCA, ACAY CAPC, ACAYK

dp[5][5] = max(dp[4][5], dp[5][4]) = max(2, 3) = 3

CAPCAK, ACAYKP이면 CAPCA, ACAYKP CAPCAK, ACAYK

dp[7][7] = max(dp[6][7], dp[7][6]) = max(3, 4) = 4

 

코드

 

import sys
input = sys.stdin.readline  # 한 줄을 통째로 입력받기 때문에 문자열의 끝에 '\n'문자 포함

first = list(input().rstrip())
second = list(input().rstrip())

x = len(first)
y = len(second)

dp = [[0] * (y+1) for _ in range(x+1)]

for i in range(1, x+1):
    for j in range(1, y+1):
        if first[i-1] == second[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[x][y])

 

문제 회고

 

이차원 배열로 선언한 DP 문제는 처음이다.. 무조건 표를 그려서 규칙성을 찾아야겠다고 생각했다.