9252 LCS 2 c++ 풀이

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4
ACAK

출처

 

LCS 1번 문제를 풀고 한달정도 지난 뒤 LCS 2 문제를 접했다. LCS 1번을 풀었었기에 2도 수월하게 풀줄 알았는데 엄청 안풀렸다.

결국 답지를 참고했다... ㅜㅜ 왜 넣으면 다 빠져나가니.. 앞으로 기록 잘 할게 머리에 잘 붙어 있어 줘

 

 

1. 먼저 LCS를 구한다. - 두 개의 문자를 이중 for문으로 비교하고 만약 같으면 dp[j][i] = dp[j-1][i-1] + 1  다르면 max(dp[j-1][i],dp[j][i-1])를 해서 dp값을 할당해 준다.

2. 거꾸로 돌아가면서 해당하는 문자를 찾아준다. 맨 마지막 dp 값부터 돌아감

3. 만약 왼쪽값이랑 달라진다면 그 부분이 바로 문자를 할당한 부분이기에 이것을 이용해서 거꾸로 거슬러 올라간다.

4. 올라가다가 0을 마주하면은 문자 찾는 로직을 종료한다.

 

 

DP는 해도 해도 어렵다...

언제 익숙해지려나 ㅋㅋ 그래도 이전에 LCS2 문제를 봤을 때 아예 이해가 안되었는데 지금은 쉽게 이해가 되는 걸 보면 실력이 늘고 있긴 하다.. 그때 당시에는 모르는데 항상 지나고보면 실력이 늘어가는 게 느껴진다. 꾸준함의 힘