[백준 1958번] LCS 3

난이도: 골드 3

문제 링크: www.acmicpc.net/problem/1958

1958번: LCS 3

문제 1958번: LCS 3

앞에서 몇 번 다루었던 LCS 문제입니다.

차이점이라면 이번에는 문자열 3개를 비교한다는 점!

따라서 dynamic programming 기법을 이용하기 위한 array 역시 3차원을 사용합니다.

기본적인 LCS algorithm에 대한 설명은 이 글을 참고하시기 바랍니다.

 

주의할 점은 문제에서 LCS가 Longest Common Subsequence를 뜻한다고 명시하고 있습니다.

즉, 연속된 문자만을 인정한다는 의미입니다.

이런 면에서, 앞서 다룬 LCS, LCS2보다, 공통 부분 문자열 문제의 확장이라고 생각하시면 되겠습니다.

 

입력받는 세 개의 문자열을 담을 string형 변수 3개를 각각 first, second, third라고 하겠습니다.

기본적인 구조는 공통 부분 문제열 문제와 동일하게 가져갑니다.

3개의 인자 중 최댓값을 return하는 int형 함수 max3를 정의하였습니다.

 

눈에 띄는 차이점은, first[i] == second[j] == third[k]가 아닐 때입니다.

3차원 배열을 상상해야 해서 생각하기 쉽지는 않지만, 위 조건이 거짓일 때, 이전 좌표의 edit_distance 값 중 가장 큰 값을 가져와야 합니다.

여기서 이전 좌표란, (i,j-1,k-1), (i-1, j, k-1), (i-1, j-1, k), (i-1, j, k), (i, j-1, k), (i, j k-1) 6개의 좌표를 뜻합니다.

기본적으로, edit_distance의 모든 좌표는 0으로 초기화가 되어 있고, first[i] == second[j] == third[k]인 경우엔 해당 edit_distance[i][j][k]를 1로 초기화합니다.

3차원이기 때문에, 위 조건이 참일 때 가져올 이전 좌표의 값을 정상적으로 불러오기 위함입니다.

코드를 늘 직관적이고 읽기 쉽게 작성하려고 노력하고 있습니다.

혹시나 제 코드 중 의미 전달이 불명확한 경우가 있다면 피드백을 주시면 감사하겠습니다.