[JAVA]1958 LCS3(dp, 골드3)

 📚 문제  

1958번: LCS 3

🔍 아이디어  

처음에는 a, b를 비교해서 lcs 문자열을 구하고 c와 비교하는 형식으로 구했더니 틀렸다.

해당 방법은 최대 값을 기준으로 하기 때문에 abc 모두에 대해서 최댓값으로 확신할 수 없다.

예를 들어(반례)

a: abcdeqfpk
b: qfpkabcde
c: qpk

와 같은 경우 a,b에 대해서 bcdef이지만 abc전체에 대해서는 qpk이다. 따라서 abc에 대해서 항상 최장 공통 문자열이 아닌 것이다.

따라서 abc모두에 대해서 3차원 배열로 계산해야 한다. 

abcdeqfpk
qfpkabcde
qpk

따로 계산한 경우 : (ab)c -> 0

같이 계산 한 경우 : abc -> 3

 

3차원 배열을 이용한 풀이는 기존의 2차원 배열과 동일하다

x-1, y-1, z-1중 최댓값을 취하고 만약 a[i]==b[j]==c[k]라면 모두에 대해서 일치하는 경우이므로 +1해 주면 된다.

 

📝 풀이 

package 백준.dynamicProgramming.lcs;

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

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

        char[] aStr = br.readLine().toCharArray();
        char[] bStr = br.readLine().toCharArray();
        char[] cStr = br.readLine().toCharArray();

        int[][][] dp = new int[aStr.length + 1][bStr.length + 1][cStr.length + 1];

        for (int i = 1; i <= aStr.length; i++) {
            for (int j = 1; j <= bStr.length; j++) {
                for (int k = 1; k <= cStr.length; k++) {
                    dp[i][j][k] = Math.max(Math.max(dp[i - 1][j][k], dp[i][j - 1][k]), dp[i][j][k - 1]);
                    if (aStr[i - 1] == bStr[j - 1] && bStr[j - 1] == cStr[k - 1]) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - 1][k - 1] + 1);
                    }
                }
            }
        }
        System.out.println(dp[aStr.length][bStr.length][cStr.length]);
    }
}