[JAVA] 백준 1958번. LCS 3 (골드3)

https://www.acmicpc.net/problem/1958

1958번: LCS 3

 

계속 이어서 LCS의 세 번째 문제입니다.

LCS를 충분히 이해했다면 쉽게 접근이 가능합니다.

 

 

최소공배수처럼 접근해서 두 문자열의 LCS를 먼저 구하고, 구한 문자열과 비교하면 구현이... 틀립니다!

 

예외가 존재하기 때문인데, 쉽게 생각해 낼 수 있는 예외는 

처음 구한 LCS와 길이가 같은 다른 문자열이 존재하는 경우도 있을 것 같고, 3개 문자열의 LCS가 두 문자열의 LCS와 다른 문자를 갖는 경우도 있을 것 같네요.

 

AAAAAAAD

ADAAAAA

AD

3개의 문자열이 있을 때 세 문자열의 LCS는 AD가 되겠지만 1번과 2번 문자열의 LCS는 AAAAAA가 되어 두 문자열의 LCS를 먼저 구할 경우 오답이 나오게 됩니다.

 

그럼 어떻게 구현해야할까요?

LCS를 구하던 방법과 똑같이 하되, 문자열이 세 개가 되었으니 3차원 배열로 확장해서 구현하면 됩니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		char[] str1 = br.readLine().toCharArray();
		int l1 = str1.length;
		char[] str2 = br.readLine().toCharArray();
		int l2 = str2.length;
		char[] str3 = br.readLine().toCharArray();
		int l3 = str3.length;

		int[][][] dp = new int[l3 + 1][l2 + 1][l1 + 1];

		for (int i = 1; i <= l3; i++) {
			char c3 = str3[i - 1];
			
			for (int j = 1; j <= l2; j++) {
				char c2 = str2[j - 1];
				
				for (int k = 1; k <= l1; k++) {
					if (c3 == c2 && c2 == str1[k - 1]) {
						dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
					} else {
						dp[i][j][k] = Math.max(dp[i][j][k - 1], Math.max(dp[i - 1][j][k], dp[i][j - 1][k]));
					}
				}
			}
		}
		System.out.println(dp[l3][l2][l1]);
	}
}

 

바로 이렇게요.

감사합니다!

 

(String의 순서를 거꾸로 비교한 건 LCS 1번, 2번에서 사용한 코드를 수정해서 작성했기 때문입니다! index만 맞는다면 어떤 식으로 반복문을 작성해도 상관없습니다.)