Search

[백준 9252] LCS 2

[백준 9252] LCS 2

Tip

예시 : ACAYKP vs CAPCAK
“”
C
A
P
C
A
K
“”
“”
“”
“”
“”
“”
“”
“”
A
“”
“”
A
A
A
A
A
C
“”
C
A
A
AC
AC
AC
A
“”
C
CA
CA
AC
ACA
ACA
Y
“”
C
CA
CA
AC
ACA
ACA
K
“”
C
CA
CA
AC
ACA
ACAK
P
“”
C
CA
CAP
CAP
ACA
ACAK
1.
문자열 s1, s2를 입력 받고 각각의 문자를 요소로 하는 배열로 저장 (인덱스를 1부터 사용하기 위해 앞에 공백 “” 문자 붙여주기)
2.
2차원 dp 테이블 생성
행은 문자열 s1의 각각의 문자로, 열은 문자열 s2의 각각의 문자로 간주
행과 열의 첫번째 요소는 공백 “”으로 한다.
테이블에 저장될 문자는 다음을 의미
문자열 s1의 해당 행까지의 부분 문자열과 문자열 s2의 해당 열까지의 부분 문자열로 만들 수 있는 부분 문자열
3.
첫 번째 행의 열, 첫 번째 열의 행 요소들은 모두 공백으로 초기화
공백만을 가지고는 만들 수 있는 부분 문자열은 없다.
3.
테이블의 나머지 요소들은 다음 규칙을 따르며 초기화시켜주면 됨.
s1[i] == s2[j] : 행과 열의 문자열이 서로 같을 경우
직전 공통 부분 문자열(테이블에서 왼쪽 대각선 바로 위)에 현재 문자 붙여주기
dp[i][j] = dp[[i - 1][j - 1] + si[i]
s1[i] != s2[j] : 서로 다를 경우
현재 행 또는 열까지의 문자열로 만들 수 있는 공통 문자열 중 가장 긴 것을 그대로 가져오기
len(dp[i - 1][j]) >= len(dp[i][j - 1]) : dp[i][j] = dp[i - 1][j] (테이블에서 바로 위)
len(dp[i - 1][j]) < len(dp[i][j - 1]) : dp[i][j] = dp[i][j - 1] (테이블에서 바로 왼쪽)
4.
전체 테이블 탐색이 완료됐으면 가장 마지막 행렬 문자열의 길이 및 문자열 출력

풀이 소스 코드

import sys si = sys.stdin.readline # 문자열 입력받아 각각의 문자로 나눠 배열로 저장 # 인덱스를 1부터 사용하기 위해 접근을 위해 맨 앞에 공백 "" 추가 s1 = [""] + list(si().rstrip()) s2 = [""] + list(si().rstrip()) # 공통 문자열을 저장할 2차원 배열 # 인덱스를 1부터 사용하기 위해 접근을 위해 맨 앞에 공백 "" 추가 dp = [[""] * len(s2) for _ in range(len(s1))] # dp 테이블 완전탐색하여 공통 문자열 구하기 for i in range(1, len(s1)): for j in range(1, len(s2)): if s1[i] == s2[j]: # 같은 문자일 경우 dp[i][j] = dp[i - 1][j - 1] + s1[i] # 대각선 왼쪽 바로 위 문자열에 현재 문자 붙이기 else: # 다른 문자일 경우 # 테이블 바로 위 또는 왼쪽 중 더 긴 문자열을 그대로 가져와 현재 행열 테이블에 저장 if len(dp[i - 1][j]) >= len(dp[i][j - 1]): dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i][j - 1] # 2차원 테이블의 가장 마지막 값을 불러와 출력 result = dp[-1][-1] print(len(result)) print(result)
Python