[백준 9251] LCS (python)

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

9251번: LCS

LCS 문제

최장 공통 부분 수열을 구하는 문제

다이나믹 프로그래밍을 통해 해결할 수 있었다.

📌문제 접근 포인트

1. 공통된 수열을 구하기 위해서 먼저 예제 입력을 표로 그려서 그려보았다. 표를 그려서 규칙을 찾아가보자.
2. 표를 보면 같은 알파벳이 나오는 부분을 기준으로 +1씩 늘어나는 구조고, 겹치지 않는 부분은 인덱스 i와 j를 기준으로 [i][j]의 값은 위쪽 칸인[i-1][j] , 위쪽 칸인[i][j-1] 두개의 값 중 큰 값을 가져가는 형태임을 확인할 수 있다.
3. 위 정보를 이용해 그대로 코드 구현하면 완성 

import sys
word1, word2 = sys.stdin.readline().strip(), sys.stdin.readline().strip()
n, m = len(word1), len(word2)
dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        if word1[i-1] == word2[j-1]: # 같은 단어가 나오면
            dp[i][j] = dp[i-1][j-1] + 1 # 같은 단어 체크
        else: # 그 외부분은
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]) # 왼쪽 위 중에 최대값 
print(dp[n][m])