백준 9251 LCS

haruponea·2021년 4월 8일
0

BOJ

목록 보기
40/41

문제 링크https://www.acmicpc.net/problem/9251

풀이
처음에 2차원 dp 배열을 만들어서 풀어봤었는데 틀렸었습니다. 처음에 했던 풀이는 dp[i][0]는 i번째 글자를 포함하는 LCS의 길이, dp[i][1] 는 i번째 문자가 다른 문자열의 몇번째 인덱스에서 나오는지 저장하는 dp배열을 만들었는데 구현도 까다롭고~~글자를 찾는 시작 인덱스를 설정해줘야 했고 글자가 없을 경우도 따로 조건을 추가해줘야 했다~~ 문제 특성상 정해가 있는 문제인것같아 풀이법을 찾아보았습니다.

정해는 다음과 같습니다.

우선 dp 테이블을 만드는데 행과 열이 각각 입력받은 문자열의 길이인 2차원 dp테이블을 만들어 줍니다.
dp[i][j]는 행의 문자열의 첫번째 글자부터 i번째 글자까지와 열의 문자열의 첫번째 글자부터 j번째 글자까지 비교하여 LCS를 저장하는 dp테이블입니다.

확정이 된 칸들은 붉은 색으로 표시했습니다. 또한 문자열 앞에 특수문자 @가 들어가는데 이것은 인덱스 범위 초과를 막기위해 넣었습니다.


두 문자열의 마지막 문자가 다르기때문에 왼쪽, 위쪽 칸과 비교하여 가장 큰 값을 넣어줍니다. 굳이 왼쪽과 위쪽인 이유는 다음과 같습니다.

예를 들어 ACAY와 CAPC를 비교할 차례가 되었을때 마지막 문자가 서로 다르므로 Y를 고려한 LCS를 선택할지 C를 고려한 LCS를 선택할지 결정해야합니다. Y를 고려한다면 ACAY와 CAP를 가지고 LCS를 만들어야 하고 C를 고려한다면 CAPC와 ACA로 LCS를 만들어야 합니다. 두 LCS의 길이중 가장 큰 값을 선택하여 dp에 저장해주면 됩니다.

정리하자면 마지막 문자가 다르다면 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 가 됩니다.


다음 열로 넘어가면서 AC 와 C를 비교해주는데 마지막 문자가 같으므로 이전 LCS에 +1을 해주면 됩니다. 이전 LCS는 (i-1, j-1)번째 칸이므로 dp[i][j] = dp[i-1][j-1] + 1이 됩니다.

같은 방식으로 테이블을 채우면 다음과 같습니다.

dp[len(s1)-1][len(s2)-1]을 출력하면 됩니다.

요약하자면 다음과 같습니다.

  1. 행과 열의 길이가 각각 입력받은 문자열의 길이인 2차원 dp테이블을 만들고 0으로 초기화한다.
  2. 2차원 테이블을 돌면서 i번째 글자와 j번째 글자가 같다면 dp[i][j] = dp [i-1][j-1] + 1 이다.
  3. 다르다면 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 이다.

python

import sys
input = sys.stdin.readline
s1 = '@'+input().strip()
s2 = '@'+input().strip()
dp = [[0]*len(s2) for _ in range(len(s1))]
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] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[len(s1)-1][len(s2)-1])

0개의 댓글