[BOJ] 백준 1958번 LCS3 (Java)

#1958 LCS3

난이도 : 골드 3

유형 : DP

1958번: LCS 3

▸ 문제

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

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

 

▸ 입력

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

▸ 출력

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

 

 

문제 풀이 

LCS 문제의 업그레이드 문제로 3개의 문자열에 공통된 가장 길이가 긴 문자열을 찾는 것으로 3차원 배열로 풀이했다. 위의 문제를 안풀어봤다면 먼저 풀고오는 것을 추천한다.

 

풀이는 2개의 문자열 비교했을 때와 같다.

1) 만약 i, j와 k가 같다면,  str1(0~i-1), str2(0~j-1), str3(0~k-1)의 LCS + 1을 해준다.

중요한 점은 str1, str2를 비교한 후 str2와 str3를 따로 비교하는 것이아니라. 3중 포문을 돌려서 i == j == k인 지점을 찾아 카운트를 해줘야하는 것이다.

 

2) 만약 i,j,k 3개의 문자열이 일치하지 않는 부분이면 (i-1, j, k) (i, j-1, k) (i, j, k-1)를 비교해서 최댓값을 가져온다

(i,j,k) = max( (i-1,j,k) , max( (i,j-1,k), (i,j,k-1) ))

memo) 계속 최댓값을 비교해가며 계산하는 부분이 좀 헷갈렸지만 큐브를 생각하니 이해가 쉬웠다.

 

풀이 코드 

// #1953 dp LCS3
import java.io.*;

public class LCS3 {

	static int[][][] dp;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s1 = br.readLine();
		String s2 = br.readLine();
		String s3 = br.readLine();
		
		System.out.println(LCS3(s1,s2,s3));
		
	}
	
	static int LCS3(String str1, String str2, String str3) {
		int n1 = str1.length();
		int n2 = str2.length();
		int n3 = str3.length();
		dp = new int[n1+1][n2+1][n3+1];
		
		for(int i=1; i<n1+1; i++) {
			for(int j=1; j<n2+1; j++) {
				for(int k=1; k<n3+1; k++) {
					if(str1.charAt(i-1) == str2.charAt(j-1) 
							&& str2.charAt(j-1) == str3.charAt(k-1)) {
						dp[i][j][k] = dp[i-1][j-1][k-1] +1;
					}else {
						dp[i][j][k] = Math.max(dp[i-1][j][k],
								Math.max(dp[i][j-1][k], dp[i][j][k-1]));
					}
					
				}
			}
		}
		
		return dp[n1][n2][n3];
	}
}