[백준/Python]9251_LCS
2021. 6. 16. 13:27ㆍ백준 알고리즘
문제
https://www.acmicpc.net/problem/9251
풀이
DP를 이용하여 풉니다.
문제에 주어진 예제를 2차원 DP 테이블에 나타내면 다음과 같습니다.
- | C | A | P | C | A | K | |
- | 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 |
입력받은 두 문자열을 순서대로 s1과 s2 변수에 저장합니다.
(len(s1) + 1) * (len(s2) + 1) 크기의 2차원 배열을 선언하고 0값으로 초기화합니다.
이중 for문을 돌면서 아래의 점화식 조건으로 값을 저장합니다.
- s1[i]와 s2[j]가 같을 때
- dp[i][j] = dp[i - 1][j - 1] + 1
- s1[i]와 s2[j]가 다를 때
- dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
최종적으로, dp[-1][-1]이 s1과 s2의 LCS가 됩니다.
코드
import sys
s1 = sys.stdin.readline().rstrip()
s2 = sys.stdin.readline().rstrip()
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
continue
if s1[i - 1] != s2[j - 1]:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[-1][-1])
'백준 알고리즘' 카테고리의 다른 글
[백준/Python]10972_다음 순열 (0) | 2021.06.17 |
---|---|
[백준/Python]2004_조합 0의 개수 (0) | 2021.06.16 |
[백준/Python]10451_순열 사이클 (0) | 2021.06.15 |
[백준/Python]10971_외판원 순회 2 (0) | 2021.06.14 |
[백준/Python]13305_주유소 (0) | 2021.06.14 |