백준 9252번 LCS 2

< 백준 9252번 LCS 2 - 마포 코딩박 >

사용한 알고리즘: DP


 두 문자열 A, B 가 주어졌을 때, 최장 공통 부분 수열(LCS) 를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 6~7)
 'dp[x][y] : 문자열 A의 0~x-1 까지, B의 0~y-1 까지 썼을 때, A의 남은 x~끝까지 와 B의 남은 y~끝까지로 만들 수 있는 LCS 길이' 로 설정하였습니다.

(2) (코드 17~30)
 dp[x][y] = max( dp[x][y+1], dp[x+1][y], dp[x+1][y+1]+ 1(A[x]=B[y]일때)or 0(A[x]!=B[y]일때)) 입니다. 이를 생각하여 dp값을 구하는 함수를 만들어주었습니다.

(3) (코드 17~30)
 만들어 놓은 dp 값을 추적하며 답을 구해주었습니다.