[BOJ] 5582 공통 부분 문자열 & 1958 LCS 3

5582번: 공통 부분 문자열

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

ABRACADABRA
ECADADABRBCRDARA

출력

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

---

 

1958번: LCS 3

문제

문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.

이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.

입력

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.

abcdefghijklmn
bdefg
efg

출력

첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.

3

---

평범한 LCS 문제랑 조금 다른 두 문제를 풀었다. LCS는 예전에 한번 풀어보고 이번에 삼성 특강을 들으면서 오랜만에 다시 만났다. 예전에 풀 때는 DP가 정말 익숙하지 않아서 문제 풀이 방법을 되게 생소해했던 기억이 있는데 이젠 이 정도 DP는 무리 없이 풀 수 있었다.

 

첫 번째 문제는 보통 LCS랑 다르게 아예 subsequence가 아니라 substring이여야 한다. LCS에서 둘의 문자가 같지 않을 때 왼쪽이나 위쪽에서 큰 값을 가져오는 부분을 빼서 쉽게 풀 수 있었다.

 

 

두 번째 문제는 문자열의 개수가 1개 늘어서 총 3개의 문자열의 LCS를 구하는 문제였다. 이 문제도 dp 배열을 2차원에서 3차원으로 늘려만 주고 똑같이 풀었다. 문자열이 2개에서 3개가 되면서 바꿀게 몇 개 없다고 방심했었는데 조건문을 잘못 걸고 있었다. 방심 ㄴ.

 

 

후기)

이런 DP는 쉽게 풀 수 있지만 조금만 더 어려워져도 그냥 우주로 날아가버린다.