[백준 9251번] LCS -python

문제 링크

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

9251번: LCS

 

풀이 -다른 블로그 참고 https://twinw.tistory.com/126

- dp 문제이다. 

- 주어진 두 문자열의 최장 공통 부분 수열을 구하는 것인데 주의해야될 점은, 연속되지 않아도 되므로 같은 길이의 다른 해가 나타날 수도 있다. 

- 이전 행의 값을 기반으로 현재 행의 값이 계산된다는 점에서 메모제이션 문제이다. 

1. 같은 문자가 나오면, 이전까지의 LCS 값(왼쪽 대각선 위) 에 + 1 

2. 문자가 다르면, 비교한 문자가 포함되어 있기 직전의 LCS 값 중 큰값 

코드로 표현하면 

1. string1[n] == string2[k] : dp[n][k] == dp[n-1][k-1] + 1

2. string1[n] != string2[k] : dp[n][k] == max( dp[n-1][k], dp[n][k-1] )

a = list(str(input()))
b = list(str(input()))

dp = [[0 for _ in range(len(a)+1)] for _ in range(len(b)+1)]

answer = 0 

for i in range(len(a)):
  for j in range(len(b)):
    # 문자가 같으면 대각선 왼쪽의 값 
    if a[i] == b[j]:
      dp[j+1][i+1] = dp[j][i] + 1 
      answer = max(answer, dp[j+1][i+1])
    # 문자가 다르면 왼쪽이나 위쪽 중 큰 값 
    else :
      dp[j+1][i+1] = max(dp[j][i+1], dp[j+1][i])

print(answer)