[ 백준 ][ 골드5 ] 9251번 - LCS ( 파이썬 Python )

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

9251번: LCS

 

문제

---

 

코드

---

a = "0"+input()
b = "0"+input()
dp = [[0] * (len(b)) for _ in range(len(a))]
for i in range(1,len(a)):
    for j in range(1,len(b)):
        dp[i][j] = dp[i-1][j-1] + 1 if a[i] == b[j] else max(dp[i-1][j],dp[i][j-1])
print(f"{dp[-1][-1]}")

 

풀이

---

DP문제들은 나를 괴롭히기 위해서 존재하는 것 같다.

분명 예전에 해결했던 문제임에도 다시 보면 해결책이 떠오르지 않는다.

이 문제가 그랬다. 다시 풀고보니 이미 해결한 문제였다..젠장

 

이 문제는 당연하게도 어떻게 보더라도 DP문제이다.

문자열의 길이는 1000까지 늘어나기 때문에 최대 100만번 탐색을 할 수 있고 시간초과는 안걸릴 것이다.

내가 알기로는 LCS2,3 이런식으로 시리즈로 있을텐데 거기서는 DP에 다른 알고리즘을 더 적용시켜서 시간을 줄여야 할 것이다.
그건 내일 해봐야 겠다.

 

DP로 해결하기 위해서 행과 열에 두 문자열의 길이만큼 배열을 할당해주는 이차원 배열을 생성한다.

 

문제의 예시로 설명하자면,

1번 행에서는 C와 A는 다르기 때문에 0, C와 C는 같으므로 1, A는 다르므로 이전 값인 C ... 이런식으로 진행한다.

어떤 기준으로 해도 상관없지만 나는 행을 내려가며 값을 채우는 느낌으로 했다.

행과 열의 값이 같으면 해당 글자를 추가하기 전의 값에 1을 더하고 값이 다르면 이전까지 비교한 값들 중 최대값을 저장한다.