[백준/파이썬]9251번 - LCS / 다이나믹

---

접근 방법

 

이문제의 유형은 다이나믹 프로그래밍으로 어떤 작은 문제로 풀 수 있을지 찾아야한다

두 문자열에 대한 선후관계는 없고 겹치는 문자를 찾는 것이 아닌, 길이만 출력하면 된다

길이가 짧을 때의 LCS를 구하고, 길이가 길어질 때 전의 결과를 그대로 가져오거나 +1하면 된다

---

풀이

 

두 문자열을 동등하게 비교하기 위해 이차원 배열을 만들고

문자열을 앞에서부터 하나씩 비교한다

문자가 다르면 arr[i-1][j]와 arr[i][j-1]중에 큰 값을 가져오고

문자가 같으면 arr[i-1][j-1]+1을 하면된다

---

정답 코드

import sys

input = sys.stdin.readline
t1 = input().strip()
t2 = input().strip()

arr = [[0] * (len(t2) + 1) for _ in range(len(t1) + 1)]

for i in range(1, len(t1) + 1):
  for j in range(1, len(t2) + 1):
    if t1[i - 1] == t2[j - 1]:
      arr[i][j] = arr[i - 1][j - 1] + 1
    else:
      arr[i][j] = max(arr[i - 1][j], arr[i][j - 1])

print(arr[-1][-1])

---

오답 풀이

 

처음에는 LCS를 몰라 배열없이 문자열의 문자를 하나하나 비교해갔지만 

다이나믹 프로그래밍이란 것을 깨닫고 이차원 배열을 만든게 중요한 점이다