백준 17218번 바로가기

나의 풀이

# 입력
import sys

read = sys.stdin.readline

A, B = read().strip(), read().strip()
n, m = len(A), len(B)
LCS = [[''] * (m + 1) for _ in range(n + 1)]

# 처리 - LCS 알고리즘 이용
for i in range(1, n + 1):
  for j in range(1, m + 1):
    if A[i - 1] == B[j - 1]:
      LCS[i][j] = LCS[i - 1][j - 1] + A[i - 1]
    else:
      if len(LCS[i - 1][j]) > len(LCS[i][j - 1]):
        LCS[i][j] = LCS[i - 1][j]
      else:
        LCS[i][j] = LCS[i][j - 1]

print(LCS[n][m])

CODE REVIEW

  1. 문제를 풀다가 도저히 해결 방법을 모르겠어서 구글링을 통해 LCS 알고리즘에 대해 알게 되었다. 아래 블로그에 그림으로 잘 설명되어있었는데, n*m matrix에 경로에 따라 +1 해가면서 빈칸을 채우는 기발한 방법으로 문제를 풀어낼 수 있었다.
  2. 숫자를 채워넣는 LCS 알고리즘을 응용해서, matrix속에 조건을 만족하면 문자열 string을 추가하는 방식으로 문제를 해결했다.
  3. dp 문제는 정말 생각지도 못한 기발한 풀이법들이 존재해서 항상 배우게 하는 것 같다.

REFERENCES