[백준] 1958번 - LCS 3 [Java]

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

 

[백준] 1958번 - LCS 3 [Java]

---

1.  아이디어

 

이전 LCS 문제에서 문자열의 개수가 3개가 된 문제로 3차원 dp 배열을 활용하면 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 9251번 - LCS [Java])

---

2. 문제풀이

 

문자열이 하나 추가된만큼 3중 for문과 max를 확인할 위치 하나만 추가하는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;

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

        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        char[] str3 = br.readLine().toCharArray();

        int N = str1.length;
        int M = str2.length;
        int K = str3.length;

        int[][][] dp = new int[1 + N][1 + M][1 + K];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                for (int k = 1; k <= K; k++) {
                    if (str1[i - 1] == str2[j - 1] && str1[i - 1] == str3[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[N][M][K]);
    }
}

---

4. 후기