G5 9251. LCS

문제 보기 :  9251번: LCS

---

문제

• 정답률 : 41%

---

작성 코드

# 입력값
str1 = input() ; len1 = len(str1)
str2 = input() ; len2 = len(str2)

# DP 테이블 초기화
dp = [[0]*(len2+1) for _ in range(len1+1)]

# DP 계산
for i in range(1,len1+1):
    for j in range(1,len2+1):
        if str1[i-1]==str2[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[len1][len2])

---

풀이

1. 두 문자열의 길이에 맞는 DP 테이블을 생성한다.

2. 각 문자를 비교하며 두 경우(같거나 다르거나)에 따라 점화식을 적용한다.

3. 모든 계산이 끝난 후, DP 테이블의 마지막 값이 최장 공통 부분 수열(LCS)의 길이를 나타낸다.