[Gold III] LCS 3 - 1958 (Java)

문제 요약

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

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

---

문제 분석

기존에 풀었던 LCS2문제의 연장선에서 3차원 배열을 사용한 문제 해결.

https://cornsilk-tea.tistory.com/64

[Gold IV] LCS 2 - 9252 (Java)

---

코드

package Week20;

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

public class BOJ_1958 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] A = br.readLine().toCharArray();
        char[] B = br.readLine().toCharArray();
        char[] C = br.readLine().toCharArray();
        int[][][] dp = new int[A.length + 1][B.length + 1][C.length+1];
        for(int i=1; i<=A.length; i++){
            for(int j=1; j<=B.length; j++){
                for(int k=1; k<=C.length; k++){
                    if(A[i-1] == B[j-1] && B[j-1] == C[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]));
                    }
                }
            }
        }
        System.out.println(dp[A.length][B.length][C.length]);
    }
}

---