9251(2)

오답 여부: o

편집 시간: 2022년 2월 24일 오후 6:02

코드

문자열 하나에 대한 dp로 접근했다. 첫번째 문자열로 dp를 한다면 아래와 같이 접근할 수 있었다.

f(x): x번째 문자열을 마지막으로 가지는 str2과의 (LCS, 마지막으로 사용한 index)

f(n) = max( f(m) ) + 1 {m | m은 정수, 0 ≤ m < n, f(n)의 index > f(m)의 인덱스}

max는 LCS가 같다면 마지막으로 사용한 index가 더 작은 것을 우선으로.

하지만 이 방식에는 예외가 있었다.

f(m) 중에서 가장 긴 부분 수열을 선택하면 index가 너무 뒤로가서 최종 LCS가 되지 못한다는 문제가 있었다. 아래의 테스트 케이스에서 실패한다.

SKDFHWEODJKSFSDFJK
WKJSDHFOWEFKJDVKSDF

두 문자열에대해서 모두 dp로 접근해야된다.

f(n, m): n길이의 str1과 m길이의 str2의 LCS

f(n, m) = max( f(n-1, m), f(n, m-1) ) → str1[n] ≠ str2[m] 인 경우

f(n, m) = f(n-1, m-1) + 1 → str1[n] == str2[m] 인 경우